Pick the fix
alt[mid] = 8 and alt[mid + 1] = 11. Where is the summit?
Choose an answer, then open Show answer below to check it.
Answer: A Strictly to the right of mid
Right: the route is still rising at mid.
A rising step at mid means you are on the climb, so the summit lies further along.
Compare alt[mid] with alt[mid + 1]. If the route is still rising there, the summit is to the right; otherwise it is at mid or to the left. Shrink until lo meets hi. Each step halves the range: O(log n) time, O(1) space.
Explain finding the summit by binary search.
Say your answer out loud, then check which of these points you covered:
The neighbour comparison tells you which side of the summit you are on.
The same idea finds some local peak in any list where neighbours differ, which is a classic follow-up.
mid + 1 is always valid because the loop keeps lo < hi.
def summit_index(alt: list[int]) -> int:
lo, hi = 0, len(alt) - 1
while lo < hi:
mid = (lo + hi) // 2
if alt[mid] < alt[mid + 1]:
lo = mid + 1 # still climbing
else:
hi = mid
return loSay which side of the summit each comparison proves you are on.
Think of your answer first, then open the hint.
What if the route has plateaus?
Equal neighbours hide the direction; worst case becomes O(n).
How do you find a value on a climb-then-descent route?
Find the summit, then binary search each side separately (one ascending, one descending).
What each operation costs: Binary Search · Linear Search
From the author
Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.
Suggest a fix if something here is wrong or out of date.