Binary Search
39 / 170Binary SearchLesson 1 of 8About 53 min
The general form of binary search, which happens to make exact-match search a one-line special case.
One loop shape covers every boundary question. It narrows a half-open range and finishes with low sitting on the first true.
def first_true(low, high, is_true): """Smallest value in [low, high) where is_true flips to True. Returns high when nothing satisfies it.""" while low < high: mid = low + (high - low) // 2 if is_true(mid): high = mid # mid might be the answer, keep it else: low = mid + 1 # mid is definitely not, discard it return low print(first_true(0, 10, lambda x: x * x >= 17))print(first_true(0, 10, lambda x: False))This searches for the first index whose value is at least 5, and prints the range at each step before returning. Type every line it prints.
def trace_search(values, target): low, high = 0, len(values) while low < high: mid = low + (high - low) // 2 print(low, high, mid) if values[mid] >= target: high = mid else: low = mid + 1 return low print(trace_search([1, 3, 5, 7, 9], 5))Write the boundary loop three times with different properties. first_at_least returns the first index whose value is at least the target, or the list length. count_below returns how many values are strictly below the target. find_exact returns the index of the target or -1, built on first_at_least.
Tests
values = [1, 3, 3, 5, 8]print(first_at_least(values, 3), first_at_least(values, 4), first_at_least(values, 9))print(count_below(values, 3), count_below(values, 0), count_below(values, 100))print(find_exact(values, 5), find_exact(values, 4), find_exact([], 1))Output
Run tests to see output.
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.