Find a peak element (binary search)

Medium TimeO(log n) SpaceO(1)

A peak is a value strictly greater than both of its neighbours, with anything off either end counting as negative infinity — so the first and last elements have one neighbour each and either can be a peak. Given nums, in which no two neighbours are ever equal, return the index of any peak. In [1, 2, 1, 3, 5, 6, 4] index 5 qualifies, and so does index 1.

Examples

Example 1

Input
nums = [1, 2, 1, 3, 5, 6, 4]
Output
5
nums[5] is 6, above the 5 before it and the 4 after it.

Example 2

Input
nums = [3, 2, 1]
Output
0
nums[0] is 3, with nothing off the left end and 2 to its right.

The Code

function findPeakElement(nums) {
  let lo = 0;
  let hi = nums.length - 1;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] < nums[mid + 1]) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}
findPeakElement([1, 2, 1, 3, 5, 6, 4]);
Done
Step through findPeakElement([1, 2, 1, 3, 5, 6, 4]) call by call

More like this

All searching examples (8) →