Discarding a half without full sortedness

Binary search needs a reason to throw away a half, and sortedness is only one possible reason.

Why it works

Why a peak can be found in log time

Compare the middle element with its right neighbor. If the middle is smaller, then the values are rising at that point, and following a rising slope must eventually reach a peak before falling off the end. So a peak exists to the right and the left half can go.

If the middle is larger than its right neighbor, the same argument runs leftward: either the middle is itself a peak, or the slope descends and a peak lies at or left of it.

Either way one half is provably peak-free-optional, meaning it can be discarded without losing every answer. That is all binary search ever needs.

1def find_peak(values):2    low, high = 0, len(values) - 13    while low < high:4        mid = low + (high - low) // 25        if values[mid] < values[mid + 1]:6            low = mid + 1        # rising, a peak lies to the right7        else:8            high = mid           # falling or flat, keep mid as a candidate9    return low10 11print(find_peak([1, 2, 3, 1]))12print(find_peak([1, 2, 1, 3, 5, 6, 4]))

Trace it· 8 min

Trace the peak search

Run find_peak on [1, 2, 1, 3, 5, 6, 4]. For each pass give mid, the comparison result as rising or falling, and the range afterward as low and high.

pass	mid	slope	low after	high after
1
2
3

Problem· 25 min

Find Minimum In Rotated Sorted Array

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1def find_peak(values):2 low, high = 0, len(values) - 13 while low < high:4 mid = low + (high - low) // 25 if values[mid] < values[mid + 1]:6 low = mid + 1 # rising, a peak lies to the right7 else:8 high = mid # falling or flat, keep mid as a candidate9 return low10 11print(find_peak([1, 2, 3, 1]))12print(find_peak([1, 2, 1, 3, 5, 6, 4]))

pass

mid

slope

low after

high after