[Binary Search] Find Peak Element

162. Find Peak Element

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

/**
 * @param {number[]} nums
 * @return {number}
 
 * Runtime	: 45 ms
 * Memory	: 41.18 MB
 */
var findPeakElement = function(nums) {  
  let ans = 0;

  for(let i = 0; i < nums.length; i++) {
    if(nums[i] > nums[i - 1] && nums[i] > nums[i + 1]){
      return i;
    }

    if(nums[ans] < nums[i]) {
      ans = i;
    }
  }

  return ans;
};

주제[Binary Search]에 적절한 해답은 아니었습니다.

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Using binary search

해답의 전문은 링크를 확인해주세요.

/**
 * Runtime	: 56 ms
 * Memory	: 42.20 MB
 */
var findPeakElement = function(nums) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2)

    const prev = nums[mid - 1] || -Infinity
    const next = nums[mid + 1] || -Infinity

    if (prev < nums[mid] && nums[mid] > next) return mid;
    else if (next > nums[mid]) left = mid + 1
    else right = mid - 1
  }
};

필자의 해답과 달리 주제[Binary Search]에 적절한 해답입니다.
Example 2를 예로

Input: nums = [1,2,1,3,5,6,4]
Output: 5

루프마다 결과는 다음과 같습니다.

첫 번째 루프: prev = 1, mid = 3, next = 5;
두 번째 루프: prev = 5, mid = 6, next = 4; +++ 정답!