1
2
3
4
5
6
7
8
9
10
11
12
1
3
6
9
12
8
4
2
[0][1][2][3][4][5][6][7]
Brute force · walk the slope
▸1for i ← 0 to n − 2:2 if arr[i] > arr[i + 1]: return i3return n − 1
state
warming up the animation
An array rises strictly to a single peak and then falls strictly away from it. Return the index of that peak in O(log n) time.
▸1for i ← 0 to n − 2:2 if arr[i] > arr[i + 1]: return i3return n − 1
line 1Walk left to right until the values stop rising. That index is the peak.