[leetcode - Java] 162. Find Peak Element (Binary Search)

1. 문제

---

- 양 옆의 요소들보다 큰 숫자 peak를 찾아라

2. 의사코드

---

peak란 nums[i]가 있다고 가정했을 때 nums[i-1]보다 크고 nums[i+1]보다도 커야한다.
1. 이진 탐색 인덱스를 설정한다
    int left = 0;
    int right = nums.length-1;
2. nums의 중간값을 taget으로 정한다
    while(left <= right) {
        int mid = (left+right)/2;
        int target = nums[mid];
    }
3. 배열 중앙 값(target)으로 이진 탐색을 하며 peak가 배열의 양 끝이라면 인덱스+1, 인덱스-1과 비교
    while(left <= right) {
        int mid = (left+right)/2;
        int target = nums[mid];

        if(target > nums[mid-1] && target > nums[mid+1]) {
            return mid;
        .
        .
        .
    }

3. 시도

---

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        // System.out.println(left + ", " + right);

        if(nums.length == 1) { // 배열 길이가 1일 때
            return 0;
        }

        while(left <= right) {
            // int mid = (left+right)/2; // 이렇게 사용했을 때 오버플로우가 발생한 경우가 있다.
            int mid = left + (right - left) / 2;
            int target = nums[mid];


            // 여기서 유효한 인덱스 범위를 설정하지 않았을 때 ArrayIndexOutOfbounds 에러가 발생했다.
            if( mid > 0 && mid < nums.length - 1 && target > nums[mid-1] && target > nums[mid+1]) {
                // System.out.println(" 1 = " + left + ", " + right + ", " + mid);
                // System.out.println("target = " + target);
                return mid;
            } else if(mid > 0 && target < nums[mid-1]) { // mid가 0보다 클 때
                // System.out.println(" 2 = " + left + ", " + right + ", " + mid);
                right = mid - 1;
            } else { // mid가 0보다 작을 때
                // System.out.println(" 3 = " + left + ", " + right + ", " + mid);
                left = mid + 1;
            }
        }

        return left;
    }
}

else로 나머지 경우를 처리를 해결할 수 있다고 생각했지만 peak가 첫 요소, 끝 요소일 경우 적절한 처리가 필요했다. 각 조건을 처리하는 if문이 많아보인다는 생각이 있었지만 조건문을 추가한 전체 코드는 아래와 같다.

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length-1;

        if(nums.length == 1) {
            return 0;
        }

        while(left <= right) {
            int mid = left + (right - left) / 2;
            int target = nums[mid];

            if(mid == 0 && nums[mid] > nums[mid+1]) { // peak가 첫 요소
                return mid;
            }
            if(mid == nums.length-1 && nums[mid] > nums[mid-1]) { // peak가 끝 요소
                return mid;
            }
            if( mid > 0 && mid < nums.length - 1 && target > nums[mid-1] && target > nums[mid+1]) {
                return mid;
            } else if(mid > 0 && target < nums[mid-1]) { // mid가 0보다 클 때
                right = mid - 1;
            } else { // mid가 0보다 작을 때
                left = mid + 1;
            }
        }

        return left;
    }
}