[리트코드] 162 - Find Peak Element(Java)

문제 설명

https://leetcode.com/problems/find-peak-element/description/

A peak element is an element that is strictly greater than its neighbors. Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks. You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array. You must write an algorithm that runs in O(log n) time.

---

🔍 접근법

배열에서 인접 요소보다 큰 피크를 찾는 가장 직관적인 방법은 선형 탐색입니다. 그러나 시간 복잡도는 O(n)으로 효율적이지 않습니다.

중요한 힌트는 문제에서 항상 peak가 존재한다는 보장입니다. 이를 바탕으로 이분 탐색 (Binary Search) 를 통해 시간 복잡도를 O(log n)으로 줄일 수 있습니다.

---

💻 코드

class Solution {
    public int findPeakElement(int[] nums) {

        if(nums.length == 1) return 0;

        int n = nums.length;

        // 경계값: 첫 요소가 peak인 경우
        if(nums[0] > nums[1]) return 0;
        // 경계값: 마지막 요소가 peak인 경우
        if(nums[n-1] > nums[n-2]) return n-1;

        // 이분 탐색 구간 설정 (경계 제외)
        int start = 1;
        int end = n - 2;

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

            // peak 조건 만족
            if(nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]){
                return mid;
            }
            // 왼쪽이 더 큰 경우 → peak는 왼쪽에 있음
            else if(nums[mid] < nums[mid - 1]){
                end = mid - 1;
            }
            // 오른쪽이 더 큰 경우 → peak는 오른쪽에 있음
            else{
                start = mid + 1;
            }
        }

        return start; // while문 종료 후 start == end → peak 위치
    }
}

---

💡 정리

• 배열에서 피크는 최소 하나 존재함이 보장됨
• 양쪽 끝에서 바로 피크를 판별할 수 있는 케이스는 먼저 처리하여 탐색 범위를 줄임
• 중앙값 mid에서 양쪽을 비교하여 더 큰 방향으로 탐색 진행 → 결국 하나의 peak에 수렴
• 종료 조건에서 start == end가 되며, 이는 반드시 peak를 가리킴

---