Medium Binary Search Binary Search
In plain English: Find the smallest number in a sorted array that has been rotated (e.g., [4,5,6,7,0,1,2]).
Compare mid to hi: if a[mid] > a[hi], the rotation point (minimum) is to the right; otherwise it is at mid or to the left.
Prompt
Given a rotated sorted array with unique elements, find the minimum element.
Try to write it from scratch before scrolling down.
Solution
def find_min(a):
lo, hi = 0, len(a) - 1
while lo < hi:
mid = (lo + hi) // 2
if a[mid] > a[hi]:
lo = mid + 1 # min is in right half
else:
hi = mid # mid could be the min
return a[lo]
# Test: find_min([4,5,6,7,0,1,2]) == 0
# Test: find_min([3,4,5,1,2]) == 1
# Test: find_min([1,2,3]) == 1