The problem. A mountain array strictly increases up to a peak and then strictly decreases (it has at least 3 values, and the peak is never at either end). Return the index of the peak. Your solution must run in O(log n) time.
arr = [0, 1, 0] -> 1
arr = [0, 2, 1, 0] -> 1
arr = [0, 2, 5, 8, 6, 3, 1] -> 3Compare arr[mid] with its right neighbour. If arr[mid] < arr[mid + 1], mid is on the rising slope, so the peak is to its right. Otherwise mid is on the falling slope — or is the peak — so the peak is at mid or to its left. "Is the next value bigger?" is yes, yes, …, no, no: the peak is the first no, and the lower-bound template finds it.
function peakIndexInMountainArray(arr) { let i = 0; while (arr[i] < arr[i + 1]) i++; // keep climbing while the next value is higher return i;}Time O(n), space O(1). It never runs off the end: the mountain always comes down before the last index.
Compare mid with its right neighbour: rising means go right, falling means the peak is here or to the left.
function peakIndexInMountainArray(arr) { let low = 0; let high = arr.length - 1; while (low < high) { const mid = low + Math.floor((high - low) / 2); if (arr[mid] < arr[mid + 1]) low = mid + 1; // still climbing: the peak is to the right else high = mid; // going down: the peak is mid or to its left } return low;}Time O(log n), space O(1). mid < high always, so mid + 1 is a real index. The array isn't sorted — but the question "am I still climbing?" is, and that's all binary search needs.
[0, 1, 0]: the peak is index 1.[1, 3, 2, 1, 0] (index 1) and [0, 1, 2, 3, 1] (index 3).