[LeetCode/JAVA] 162. Find Peak Element

문제

주변 보다 큰 요소를 peak 요소라 부르는데, 이 peak이라는 요소의 아무 인덱스나 반환하는 문제이다. 여기서 O(log n)을 만족하는 알고리즘을 사용해야한다.

풀이

배열의 요소의 주변은 왼쪽 오른쪽으로 생각할 수 있다. 이 둘 보다 클 때 peak이라는 요소가 되므로 이에 알맞는 알고리즘을 선택해야했고, 이분 탐색(bineary search) 알고리즘을 사용해서 풀이할 것이다.

시작은 배열의 시작 0과 끝 nums.length - 1 에서 부터 시작할 것이다.

배열의 중간을 구하기 위해 ( 왼쪽 인덱스 + 오른쪽 인덱스 ) / 2 를 계산하여 중간 인덱스 값을 구하고, 이 중간 인덱스의 위치한 nums의 요소를 오른쪽 요소와 비교한다. 만약 중간 값이 작다는 것은 오른쪽 값이 더 크므로, 왼쪽 인덱스를 중앙 + 1로 옮기고 중간 값이 더 클경우 오른쪽 인덱스를 중앙으로 옮긴다. 이를 반복한다.

코드

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;
    }
}