Peak Index in a Mountain Array
Problem
You are given an array that strictly increases then strictly decreases. Return the index i such that arr[i] is the maximum (the peak).
arr = [0,2,4,6,5,3,1]3def peakIndexInMountainArray(arr):
lo, hi = 0, len(arr) - 1
while lo < hi:
mid = (lo + hi) // 2
if arr[mid] < arr[mid + 1]:
lo = mid + 1
else:
hi = mid
return lofunction peakIndexInMountainArray(arr) {
let lo = 0, hi = arr.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] < arr[mid + 1]) lo = mid + 1;
else hi = mid;
}
return lo;
}class Solution {
public int peakIndexInMountainArray(int[] arr) {
int lo = 0, hi = arr.length - 1;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (arr[mid] < arr[mid + 1]) lo = mid + 1;
else hi = mid;
}
return lo;
}
}int peakIndexInMountainArray(vector<int>& arr) {
int lo = 0, hi = (int)arr.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (arr[mid] < arr[mid + 1]) lo = mid + 1;
else hi = mid;
}
return lo;
}Explanation
A mountain array goes up, hits one peak, then comes down. The slow way is to scan every element and find the largest, but we can be much smarter because the shape lets us use binary search.
At any middle index mid, we compare it to its right neighbor arr[mid + 1]. If arr[mid] < arr[mid + 1] we are still climbing the upslope, so the peak must be somewhere to the right — we move lo = mid + 1.
Otherwise we are on the downslope (or standing on the peak), so the peak is at mid or to its left — we move hi = mid. We never discard the peak, only narrow the window until lo and hi meet.
Example: arr = [0,2,4,6,5,3,1]. At mid = 3, arr[3] = 6 and arr[4] = 5, so 6 > 5 — downslope, move hi left. The window keeps shrinking until both pointers land on index 3, the peak.
Each step throws away half the array, so we find the peak in about log n comparisons instead of scanning all n elements.