[LeetCode75] Find Peak Element

https://leetcode.com/studyplan/leetcode-75/

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

 

class Solution {
    public int findPeakElement(int[] nums) {
        // 왼쪽 끝
        int left = 0;
        // 오른쪽 끝
        int right = nums.length - 1;
        
        while (left < right) {
            // 가운데 인덱스
            int middle = left + (right - left) / 2;
            
            // 중간 값이 피크인지 확인
            if (nums[middle] > nums[middle + 1]) {
                // 왼쪽 절반에 피크가 있을 수 있음
                right = middle;
            } else {
                // 오른쪽 절반에 피크가 있을 수 있음
                left = middle + 1;
            }
        }
        
        // left과 right가 일치할 때 피크
        return left;
    }
}

 

포인트

• nums[i] != nums[i+1] ➡ array는 증가하거나 감소하는 순서로 정렬되어 있고, peak가 적어도 하나는 존재하게 됨.
• nums[-1] = nums[n] = -∞ ➡ array의 양 끝도 peak가 될 수 있음.
• 반씩 줄이면서 탐색을 반복하다가 left == right 지점이 오면 거기가 peak이라는 의미이므로 left 반환