Binary search

The idea

You met recursive binary search in Module 5. Here is the loop version, which uses O(1) space, and its variants. The list must be sorted. Look at the middle item. If it is the target, stop. If it is smaller than the target, the target can only be to the right, so discard the left half; otherwise discard the right half. Each step halves the range, so a million items need at most 20 steps (2²⁰ is about a million).

The exact loop

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1          # the search range is nums[lo..hi], both included
    while lo <= hi:                    # <= : a one-item range must still be checked
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1               # mid is too small: drop it and everything left
        else:
            hi = mid - 1               # mid is too big: drop it and everything right
    return -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))   # Output: 3
print(binary_search([1, 3, 5, 7, 9, 11], 4))   # Output: -1

The invariant (a fact that stays true every round) is: if the target is anywhere, it is inside nums[lo..hi]. Every line keeps that true, and the range shrinks by at least one each round, so the loop ends. When lo passes hi, the range is empty and the target is missing.

Off-by-one mistakes

• while lo < hi with inclusive bounds: the last remaining item is never checked.
• lo = mid instead of lo = mid + 1: when hi = lo + 1, mid equals lo and the loop runs forever.
• hi = len(nums) with inclusive bounds: nums[mid] can go past the end.
• In Java or C++, (lo + hi) / 2 can overflow a 32-bit int for huge arrays; write lo + (hi − lo) / 2. Python integers do not overflow, but interviewers like this point.

Lower bound and upper bound

Often you need a position, not just "found or not". The lower bound of x is the first index whose value is ≥ x; the upper bound is the first index whose value is > x. Both are also the places to insert x and keep the list sorted. These use a half-open range [lo, hi), where hi is NOT included, and the loop runs while lo < hi. The same template finds "the first index where a condition becomes true", which is the heart of Topic 5.

def lower_bound(nums, x):
    lo, hi = 0, len(nums)              # half-open: nums[lo..hi-1]
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < x:
            lo = mid + 1
        else:
            hi = mid                   # mid might be the answer: keep it
    return lo

nums = [1, 2, 4, 4, 4, 7]
print(lower_bound(nums, 4), lower_bound(nums, 5), lower_bound(nums, 9))   # Output: 2 5 6

Python's bisect module does exactly this in C: bisect.bisect_left(nums, x) is the lower bound and bisect.bisect_right(nums, x) is the upper bound. bisect.insort(nums, x) inserts x in order (the search is O(log n), but inserting into the list shifts items, O(n)). Since Python 3.10 these functions also accept key=.

from bisect import bisect_left, bisect_right

nums = [1, 2, 4, 4, 4, 7]
print(bisect_left(nums, 4), bisect_right(nums, 4))   # Output: 2 5
print(bisect_right(nums, 4) - bisect_left(nums, 4))  # Output: 3   (how many 4s)

First and last position of a value

With duplicates, the first position of x is lower_bound(x) if that index holds x; the last position is upper_bound(x) − 1. Two binary searches, O(log n) total. Scanning left and right from any match would be O(n) when the whole list is x.

Search in a rotated sorted array

A sorted list of distinct values is rotated at some unknown point, for example [4, 5, 6, 7, 0, 1, 2]. It is no longer sorted, but at any mid, at least one of the halves nums[lo..mid] and nums[mid..hi] IS sorted. Check which: if nums[lo] ≤ nums[mid], the left half is sorted. If the target lies within that sorted half's range, search there; otherwise search the other half. Still O(log n).

Common mistakes

• Running binary search on unsorted data. Fix: sort first (O(n log n)) or use a set or dict for single lookups.
• Mixing the inclusive template (lo <= hi, hi = mid − 1) with the half-open one (lo < hi, hi = mid). Fix: pick one template and keep all four lines consistent.
• Returning any match when the problem asks for the first one. Fix: use the lower bound, and keep searching left after a match.
• Using nums.index(x) or "x in nums" inside a loop, which is O(n) each. Fix: bisect for sorted data.
• Forgetting the empty list. Fix: with hi = len(nums) − 1 = −1 the loop simply does not run; check that your code returns the right value.