The problem. A peak is a value strictly bigger than its neighbours. Given an array nums where no two neighbours are equal, return the index of any peak. Imagine nums[-1] and nums[n] are −∞, so a value at either end only needs to beat its one neighbour. Your algorithm must run in O(log n) time.
nums = [1, 2, 3, 1] -> 2
nums = [1, 2, 1, 3, 5, 6, 4] -> 5 (or 1)
nums = [10, 20, 30, 40, 50] -> 4 (always rising: the last value is a peak)Stand at mid and look right. If nums[mid] < nums[mid + 1], the ground rises to the right. Keep walking right: either it keeps rising until the end — and the last value is a peak, because nums[n] is −∞ — or it falls somewhere, and the top before the fall is a peak. Either way a peak exists to the right, so drop the left half. If instead nums[mid] > nums[mid + 1], the same argument walking left says a peak is at mid or to its left. The array isn't sorted and has many peaks, but each comparison still safely throws away half.
function findPeakElement(nums) { for (let i = 0; i + 1 < nums.length; i++) { if (nums[i] > nums[i + 1]) return i; // the first downhill step: nums[i] beat both neighbours } return nums.length - 1; // always rising: the last value is a peak}Time O(n), space O(1). Why is the first downhill step a peak? Everything before it was rising, so nums[i] is also bigger than nums[i - 1].
Compare mid with its right neighbour and move toward the higher side.
function findPeakElement(nums) { let low = 0; let high = nums.length - 1; while (low < high) { const mid = Math.floor((low + high) / 2); if (nums[mid] > nums[mid + 1]) { high = mid; } else { low = mid + 1; } } return low;}Time O(log n), space O(1). The range low..high always contains a peak, and it shrinks every step, so when one index is left, it's a peak. (In JavaScript, (low + high) / 2 is safe; in Java and C++ use low + (high - low) / 2.)
[-2147483648] or values next to INT_MIN: compare neighbours, never add them.