[LeetCode] Merge Sorted Array - Javascript

Find Peak Element

[양옆의 요소와 비교해 큰 수 인지 확인]

제약 조건 

1 <= nums.length <= 1000
-2^31 <= nums[i] <= 2^31 - 1
nums[i] != nums[i + 1] for all valid i.

 

Example

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

ex2) 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.

문제 접근 방식

문제 설명에 Y"ou may imagine that nums[-1] = nums[n] = -∞"라는 설명이 있다.
즉 nums 배열의 -1 인덱스와 n 인덱스는 가장 최솟값을 가진다고 되어 있다는 의미이다.
이 점을 생각해 해당 문제를 이진 탐색으로 풀 수 있다.

맨 처음 while 반복문으로 start가 end보다 커질 때 까지 반복한다.

mid는 배열의 중간의 값으로 초기화 되도록
mid = Math.floor((start + end) / 2); 연산을 수행한다.

그 후 mid의 이전 인덱스와 이후 인덱스를 비교해 mid가 양옆 요소보다 큰지 확인하고 크다면 해당 인덱스를 리턴한다.
만약 아니라면 mid의 요소 값이 left 보다 크다면 end를 mid-1로 값을 업데이트하고, 작다면 start를 mid+1 값으로 

업데이트를 하여 절반을 날려버린다.

 

이런 방식으로 접근하면 왼쪽이나 오른쪽의 절반 중 한쪽에 요소가 양옆보다 큰 수가 없어 다른 한쪽을 버려버리면 안 될 것 같지만,
이렇게 해도 되는 이유는 nums[-1]과 nums[n] 인덱스는 -Infinity 값을 가지기 때문에 배열의 맨 끝까지 가게 되면 어차피 최솟값과 요소의 값을 비교하기에 무조건 양옆보다 큰 요소가 나온다.

 

solve 전체 코드  

/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function(nums) {
    let start = 0, end = nums.length - 1
    let mid = 0;
    
    while (start <= end) {
        mid = Math.floor((start + end) / 2);
        
        const val = nums[mid];
        const left = nums[mid - 1] || -Infinity
        const right = nums[mid + 1] || -Infinity
        
        if (val > left && val > right) return mid;
        if (left > val) {
            end = mid - 1
        } else {
            start = mid + 1
        }
    }

    return 0;
};