[leetcode] 162. Find Peak Element

 

일단 Peak이란 극댓값으로 양옆보다 큰 값을 의미한다.

배열에서 극댓값을 찾는 방법은 두 가지가 있는데 첫번째는 순차 탐색이다.

순차 탐색의 경우 처음부터 끝까지 양옆을 비교해가며 극댓값을 찾는 것이다. 시간복잡도는 O(n)이다.

 

또 다른 방법은 이진 탐색을 사용하는 것이다.

극댓값을 찾는다는 것은 결국 배열에서 가장 큰 값을 찾는 것이다.

 

아래 코드처럼 배열의 left, right 인덱스를 두고 이 인덱스들을 바탕으로 중간값을 찾아 중간값과 중간 옆 값을 비교합니다.

비교 결과를 바탕으로 인덱스를 옮겨가며 가장 큰 값의 인덱스를 찾습니다.

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}