Find the top of the hill
Find the peak of a list that climbs and then falls, by comparing the middle with its neighbour to see which way is uphill. About 13 minutes.
A list that has a top
Think of walking up a hill and down the other side, taking a reading of the height at each step. The readings rise until the top, then fall. The list 1, 3, 6, 9, 7, 4, 2 is such a hill. Where is the top?
You can't use sorted-order tricks, since the list isn't sorted. But you can use the slope. Stand at any point and look one step ahead: if the next height is more, the top lies ahead of you. If it is less, you have passed the top, or you are standing on it.
if nums[mid] < nums[mid + 1]:
print("still climbing")
else:
print("at the top, or past it")Look at the middle, 10, and the next value, 12. It rises, so the top is to the right of 10.
Why mid + 1 is always safe
The loop keeps low strictly below high, so the middle is always strictly below high, which means mid + 1 is a real position. You never read past the end.
And when low meets high, only one position is left, and it must be the top: everything before it was climbing, and everything after it was falling. The loop ends with the answer in low.
The middle value is 5 and the next value is 8. Where is the top?
- ATo the right of the middle, because the ground is rising
- BTo the left of the middle
- CAt the middle
Show the answer
To the right of the middle, because the ground is rising. A rising step means you haven't reached the top yet.
Top of the hill
heights is a list of whole numbers that strictly increases up to one top and then strictly decreases (either side of the top can be empty, and no two neighbouring values are equal). Return the position of the top.
heights = [1, 3, 6, 9, 7, 4, 2] → 3
1 ≤ length ≤ 100,000 · 0 ≤ value ≤ 1,000,000,000