LeetCode 162: 이분 탐색으로 Peak Element 찾기

오른쪽으로 올라가는지 확인합니다

양옆의 값보다 큰 원소를 peak라고 합니다. 그런 원소가 여러 개면 어느 인덱스를 반환해도 되지만 O(log n) 시간에 찾아야 합니다.

이 조건에 맞춰 이분 탐색을 사용했습니다. 탐색 범위를 배열의 처음과 끝으로 잡고 중간 위치 mid의 값과 바로 오른쪽 값을 비교합니다.

nums[mid] < nums[mid + 1]이면 오른쪽으로 값이 올라가므로 왼쪽 경계를 mid + 1로 옮깁니다. 그렇지 않으면 mid도 후보에 포함해 오른쪽 경계를 mid로 옮깁니다. 양쪽 경계가 같아질 때까지 반복하고 남은 위치를 반환합니다.

배열 전체가 정렬되어 있지 않아도 여기서는 이분 탐색을 쓸 수 있습니다. 문제에서는 이웃한 값이 다르고 배열 바깥의 값을 음의 무한대로 봅니다. 올라가는 쪽을 따라가면 언젠가 내려가거나 배열 끝에 도달하므로, 남긴 구간에 봉우리가 있습니다.

코드

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

        while (r > l) {
            int mid = (l + r) / 2;
            if (nums[mid] < nums[mid + 1]) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return r;
    }
}