[LeetCode] 162 Find Peak Element JavaScript

문제 링크

Find Peak Element - LeetCode

 

문제 유형

이진 탐색 (Binary Search)

 

문제 풀이

이 문제는 완전 탐색을 통해 배열 내의 가장 큰 값을 찾고, 전/후 값을 비교해 peak elements인지 확인하는 방법이 있다. 이 경우, 시간 복잡도는 O(n)이다.
이 문제는 O(log n)의 시간복잡도를 갖도록 구현해야 하므로 이진 탐색을 이용하여 peak elements를 찾는다면 O(log n)의 시간 복잡도로 문제를 해결할 수 있다.

이 문제에서 유의할 점은 다음과 같다.

• 다양한 peak elements가 나올 수 있다.
• nums[-1] = nums[n] = -∞ 이므로 배열의 맨 처음/끝 값도 peak element가 될 수 있다.

nums = [1, 2, 1, 3, 5, 6, 4] 가 주어졌다고 하자.

1. 첫 이진 탐색의 범위는 배열의 처음과 끝이다. 처음과 끝의 중간값인 nums[pivot]과 pivot 다음 값인 nums[pivot + 1]을 비교한다. 다음 값이 더 크므로 다음 탐색 범위를 (pivot + 1) ~ 6으로 설정한다.

2. nums[pivot]과  nums[pivot + 1]을 비교한다. pivot의 값이 더 크므로 탐색 범위를 4 ~ pivot으로 설정한다.

3. nums[pivot]과 nums[pivot + 1]을 비교한다. pivot 다음 값이 더 크므로 탐색 범위를 (pivot + 1) ~ 5로 설정한다.

4. left와 right가 같으므로 탐색이 종료된다. left나 right를 반환하여 peak element의 index를 출력한다.

 

코드

// Binary Search (Time Complexity: O(log n))

var findPeakElement = function(nums) {
    let left = 0;
    let right = nums.length - 1;
    
    if (nums.length === 1) return 0;
    
    while (left < right) {
        const pivot = Math.floor((left + right) / 2);
        const num = nums[pivot]; // 해당 넘버
        const nextNum = nums[pivot + 1]; // pivot 오른쪽의 넘버
        if (num < nextNum) {
            left = pivot + 1;
        } else {
            right = pivot;
        }
    }
    return left;
};

 

참고

https://www.youtube.com/watch?v=zChSh4yOOCg