Medium Binary Search Binary Search
In plain English: Find any element in an array that is bigger than both its neighbors.
If a[mid] < a[mid+1], a peak must exist to the right (values must eventually drop at the boundary). Move toward the rising side.
Prompt
Given an array where no two adjacent elements are equal, find any peak element (strictly greater than its neighbors). Return its index.
Try to write it from scratch before scrolling down.
Solution
def find_peak(a):
lo, hi = 0, len(a) - 1
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < a[mid + 1]:
lo = mid + 1 # peak is to the right
else:
hi = mid # mid could be the peak
return lo
# Test: find_peak([1,2,3,1]) == 2
# Test: find_peak([1,2,1,3,5,6,4]) in (1, 5)