First and last occurrence

The search from the first two lessons finds a copy of the target. But often we need a specific copy: the first one, the last one, or the number of copies. This lesson shows a different way to think about binary search, which the rest of this station uses.

When the target appears more than once

Take t = 7. The basic search returns whichever 7 it happens to land on. On the 16-value list in the figure below, it lands on index 3, the first copy, but only by luck. On [7, 7, 7, 7, 7] it returns index 2. Which copy you get depends on the length of the list, not on what you asked for. Code that depends on this will break.

One fix is to find any 7 and then step left until the value changes. But that costs one read for each copy. If the list has a million 7s, it costs a million reads, and the search is no longer O(log n). We want to find the first 7 in O(log n) reads, however many copies there are.

Search for a boundary, not a value

Instead of asking “is this the target?”, ask a yes-or-no question about each index:

Because a is sorted, once a[i] >= t is true, it stays true for every later index. So the answers are a block of F (false) followed by a block of T (true). There is exactly one point where F changes to T, and binary search can find it. If the value at that point equals t, it is the first copy. If not, t is not in the list.

To find the last copy, ask a[i] > t instead. Its first T is the first value bigger than t. So the last copy of t, if there is one, is just before it. The number of copies is the distance between these two points.

Look at the row of F and T labels under the list. A label changes from ? to F or T only when the search has proved it. The window is exactly the part still marked ?.

The half-open window

This search is simplest with a half-open window, written [lo, hi). Here lo is the first index we have not settled yet, and hi is the first index we know is T. At the start hi = n, which is one past the end of the list. It stands for “no T found yet”.

def first_at_least(a, t):
    """Smallest i with a[i] >= t, or len(a) if there is none."""
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] >= t:
            hi = mid          # mid may be the first T: keep it
        else:
            lo = mid + 1      # mid is F: drop it
    return lo                 # lo == hi: the boundary

At the start, both parts of this statement are about empty ranges, so they are true. If mid is T, every index from mid onwards is T, so we set hi = mid. If mid is F, every index up to mid is F, so we set lo = mid + 1. Since lo ≤ mid < hi, both updates make the window smaller. When lo == hi, nothing is unknown, and lo is the boundary.

Notice the difference between the two updates. hi = mid keeps mid, because it might be the answer. lo = mid + 1 removes mid, because an F is never the answer. Lesson 6 shows what goes wrong if you mix these up.

bisect_left and bisect_right

This loop is almost exactly what Python’s bisect module does:

Both functions accept lo and hi arguments to search only part of a list. Since Python 3.10, they also accept a key function, so you can search a list of records sorted by one field. insort inserts a value and keeps the list sorted. Finding the place takes O(log n), but moving the later items along takes O(n). So insort does not make a list into a fast sorted container.