Find a Peak

The Idea

A peak is any index at least as high as its neighbours, and an unsorted array still has one. Compare mid with the element just right of it. If the ground rises, a peak must lie to the right: the values either climb to the edge or turn over on the way. If it falls, mid itself may be the peak, so keep it. Each test halves the range and still lands on a real peak.

Real-World Example

Walking a ridge in thick fog. You cannot see the summit, but if your next step is uphill there is a top ahead of you, and if it is downhill you have just walked over one. Either way, half the ridge stops mattering.

The Code

def find_peak(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1     # uphill: a peak sits to the right
        else:
            hi = mid         # downhill: mid may be the peak itself
    return lo                # lo == hi, and that index is a peak

print(find_peak([1, 3, 6, 4, 2]))   # 2

while lo < hi:
  mid = (lo + hi) // 2
  if nums[mid] < nums[mid + 1]:
      lo = ___
  else:
      hi = mid
return lo