https://leetcode.com/problems/find-peak-element/?envType=study-plan-v2&envId=top-interview-150

162. Find Peak Element

⭐ 문제

주어진 0-인덱스 정수 배열 nums에서, "peak element"는 해당 요소가 그 주변 요소보다 엄격하게 큰 요소를 의미합니다. 이제 주어진 배열에서 어떤 피크 요소를 찾고, 그 인덱스를 반환해야 합니다. 배열에 여러 개의 피크가 있는 경우, 어떤 피크의 인덱스든 반환해야합니다

nums[-1] = nums[n] = -∞로 가정할 수 있습니다. 다시 말해, 배열 밖에 있는 이웃보다 요소가 항상 엄격하게 큰 것으로 간주됩니다.

O(log n) 시간 내에 실행되는 알고리즘을 작성해야 합니다.

🤔 접근 방향

이진 탐색 알고리즘을 활용하여 배열에서 피크 요소를 찾습니다. 중간 지점을 선택하고 이웃한 요소들과 비교하여 이동하는 방식을 사용하여 O(log n) 시간 내에 피크 요소를 신속하게 식별합니다.

✍️ 의사 코드

1. 처음에는 두 개의 포인터, left와 right, 를 사용하여 배열의 처음과 끝 인덱스를 가리킵니다.
2. 이진 탐색을 시작합니다. 탐색 범위의 중간 지점을 계산하기 위해 mid 변수를 사용하며, 중간 지점은 left와 right 사이에 있습니다.
3. 중간 지점의 요소(nums[mid])와 그 다음 요소(nums[mid + 1])를 비교합니다.
   3.1 만약 현재 요소가 다음 요소보다 크다면, 이는 피크 요소의 가능성이 있는 것을 나타냅니다. 따라서 탐색 범위를 왼쪽 절반으로 좁힙니다.
   3.2 그렇지 않으면, 다음 요소가 현재 요소보다 크기 때문에 피크 요소는 오른쪽 절반에 있을 가능성이 있으므로 탐색 범위를 오른쪽 절반으로 좁힙니다.
4. 이렇게 탐색 범위를 좁혀가며 중간 지점을 다시 계산하고, 다음 요소와 비교하며 이진 탐색을 반복합니다.
5. left와 right가 같은 위치에서 루프가 종료될 때, 이 위치는 피크 요소의 인덱스입니다. 이 인덱스를 반환합니다.

✅ 나의 풀이

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

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] > nums[mid + 1]) {
                // 현재 요소가 다음 요소보다 크면 왼쪽 부분을 탐색
                right = mid;
            } else {
                // 다음 요소가 현재 요소보다 크면 오른쪽 부분을 탐색
                left = mid + 1;
            }
        }

        // left와 right가 같은 위치에서 루프가 종료되면 피크 요소의 인덱스가 됩니다.
        return left;
    }
}

🖥️ 결과

Runtime 0ms