leetcode link

Medium

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.

Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Constraints:

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• nums[i] != nums[i + 1] for all valid i.

---

162. 피크 요소 찾기

중간 난이도

피크 요소는 이웃한 요소보다 엄격하게 큰 요소입니다.

0으로 인덱싱된 정수 배열 nums이 주어졌을 때, 피크 요소를 찾고 그 인덱스를 반환하세요. 배열에 여러 피크가 있으면, 피크 중 하나의 인덱스를 반환하세요.

nums[-1] = nums[n] = -∞라고 가정할 수 있습니다. 즉, 배열 밖의 이웃 요소와 비교할 때, 항상 엄격하게 더 크다고 간주됩니다.

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

예제 1:
입력: nums = [1,2,3,1]
출력: 2
설명: 3은 피크 요소이며, 함수는 인덱스 번호 2를 반환해야 합니다.

예제 2:
입력: nums = [1,2,1,3,5,6,4]
출력: 5
설명: 함수는 피크 요소가 2인 인덱스 번호 1이나 피크 요소가 6인 인덱스 번호 5를 반환할 수 있습니다.

제약 사항:

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• 모든 유효한 i에 대해 nums[i] != nums[i + 1]

Solution

숫자들은 피크를 중심으로 양 옆의 숫자들은 내려가는 마치 산 같은 모양이 된다.
이것과 문제에 주어진 아래 규칙을 활용하면 쉽게 풀 수 있다.

nums[-1] = nums[n] = -∞는 다음을 의미한다.

• nums[-1] < nums[0]
• nums[n-1] > nums[n]

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]) {
                left = mid + 1; // 피크가 mid+1 이후에 있다고 판단
            } else {
                right = mid; // 피크가 mid 이하에 있다고 판단
            }
        }
        //// 반복문이 종료되면 left와 right는 같은 위치를 가리키며, 이 위치는 피크의 인덱스임
        return left;
    }

}