[Binary Search, Medium] Find Peak Element

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

마찬가지로 이분탐색 문제고 문제 자체에서 O(log n)시간복잡도를 제시한다.

엄격하게 큰 원소를 찾아야 하는데,
배열 밖에 있는 것보다는 항상 크다고 가정한다고 한다.

가장 중요한 문제는 정렬이 불가능한데 start/end에 대한 증가 및 감소 구간을 어떻게 설정하느냐? 이다.

그것은 피크에 대한 정의로 알 수 있다.

• mid > mid + 1이면, 현재 mid가 더 높으므로 피크가 될 가능성이 있다 -> end = mid
• 그 외의 경우, 현재 mid가 더 낮으므로 내 오른쪽이 피크가 될 가능성이 있다 -> start = mid + 1

왜 그 외의 경우는 더 낮다고 가정하냐면 아래 조건이 있기 때문
nums[i] != nums[i + 1] for all valid i.

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

        while (start < end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] > nums[mid + 1]) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }

        return start;
    }
}