문제

https://leetcode.com/problems/find-peak-element/description/?envType=study-plan-v2&envId=top-interview-150

해결 방법

• peak element를 찾아야 하는데, 배열 전체를 한 번 순회할 수도 없는 문제 ( O(log n)의 시간 복잡도로 끝내야 하기 때문 )
• log n의 시간복잡도를 보았을 때, 이분탐색으로 해결하는 방법을 생각해봄
• 배열을 순회하는 과정에서 for문을 사용하는 대신, 이분탐색으로 순회하여 문제를 해결할 수 있었음
• 배열의 크기가 10으로 주어졌다고 가정해보면
  1. left = 0, right = 9를 기준으로 mid = (9 + 0) / 2 = 4로 잡음
  2. nums[4]가 peak element인지 체크
  3. peak element라면 더 이상의 조회를 멈추고, 4 return
  4. peak element가 아니라면 구간을 2개(0~3, 5~9)로 나누어 다시 조회
  5. 이 방법을 통해 log n의 시간복잡도로 peak element를 찾을 수 있었음

코드

class Solution {
    private static int answer;

    public int findPeakElement(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }

        answer = -1;
        binarySearch(nums, 0, nums.length - 1, nums.length - 1);
        return answer;
    }

    private void binarySearch(int[] nums, int left, int right, int end) {
        // 답을 찾은 경우
        if (answer != -1) return;
        if (left > right) return;

        int mid = (left + right) / 2;
        if (mid == 0) {
            if (nums[mid] > nums[mid + 1]) {
                answer = mid;
                return;
            }
        } else if (mid == end) {
            if (nums[mid] > nums[mid - 1]) {
                answer = mid;
                return;
            }
        } else if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
            answer = mid;
            return;
        }

        binarySearch(nums, left, mid - 1, end);
        binarySearch(nums, mid + 1, right, end);
    }
}

결과