Problem Statement
Peak Index in a Mountain Array
Picture a mountain. The numbers go up, up, up to one high point, then go down, down, down. That high point is the peak: it is bigger than the number on its left and bigger than the number on its right. Our job is to find the position (the index) of that peak. An index is just the slot number in the list, starting at 0. We could walk through every number one by one until we find the top, which takes O(n) time (n is how many numbers there are). But we can do better with binary search. Binary search means we keep looking at the middle of our range and throw away the half that cannot hold the answer, so the range shrinks fast. The trick here: at the middle spot, we compare it to the number just to its right. If the middle is smaller than its right neighbor, we are still walking uphill, so the peak is somewhere to the right. If the middle is bigger than its right neighbor, we are already going downhill or standing on the peak, so the peak is at the middle or to the left.
Signals to notice
Brute force first
Linear scan for max — O(n).
The key insight
Binary search: if nums[mid] < nums[mid+1], ascending (peak right). Else descending (peak left/at mid). O(log n).
Trace it on arr=[3,4,5,1]
init: left=0, right=3 mid=1: arr[1]=4 < arr[2]=5 -> ascending, left=mid+1=2 mid=2: arr[2]=5 > arr[3]=1 -> descending, right=mid=2 left==right==2 -> exit loop return left = 2 (peak arr[2]=5)
What must stay true
The array is bitonic. Comparing mid with mid+1 determines which slope you're on.
Shape of the loop
left, right = 0, len(arr) - 1
while left < right:
mid = (left + right) // 2
if arr[mid] < arr[mid + 1]: left = mid + 1 # ascending, peak right
else: right = mid # descending/at peak
return leftPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Comparing with both neighbors — only mid vs mid+1 is needed.