Lower bound, upper bound and first-true search

A lower bound is the first position in a sorted array whose value is at least x, and an upper bound is the first position whose value is greater than x. Both are cases of one search, the first-true search: given a test that is false for the first positions and true for all the rest, it finds the first position where the test is true. When x repeats, its copies fill exactly the positions from the lower bound up to, but not including, the upper bound, so two searches give the first copy, the last copy and the count. When x is missing, both bounds return the same position: where x would be inserted to keep the array sorted. Python’s bisect_left and bisect_right compute these two bounds.

When one position is not enough

The search of the previous lesson stops at the first copy of x it happens to probe. With repeated values that copy can be anywhere in the run: in the list 12, 15, 15, 15, 18 it may report any of the three 15s. Many questions need a particular position instead:

• the first or the last occurrence of a value;
• how many times a value occurs, or how many values fall in a range such as marks from 60 to 75;
• where a missing value would go, to insert it or to find its neighbours on both sides.

Each of these is a lower bound, an upper bound or a difference of the two, and each costs about 20 probes on a million values instead of a scan.

The first-true search

The first-true search works on any test of positions that is false up to some point and true from there on, for example “is a[i] >= 15?” on a sorted list. It keeps a half-open range [lo, hi) of positions it has not decided yet, with this invariant: the test is false at every position before lo and true at every position from hi on. It starts with lo = 0 and hi = n, where nothing is decided, and repeats one step while lo < hi:

• test the middle position mid;
• if the test is true there, mid could be the first true position, so keep it: hi = mid;
• if it is false, mid and everything before it are false: lo = mid + 1.

When lo meets hi, every position before it is false and every position from it on is true, so lo is the answer. If no position passes the test, the answer is n, one past the end. The undecided range at least halves on every probe, so the search makes at most ⌊log₂ n⌋ + 1 probes, the same bound as before.

The lower bound of x is this search with the test a[i] >= x, and the upper bound uses a[i] > x. That single character is the whole difference between them. The same search also finds the first broken commit in a history, or an integer square root, because each is a test that turns true once.

Lower bound and upper bound, traced

This program writes the search once, builds both bounds on it, prints every probe of the lower bound of 15, and then checks both functions against bisect on 2,000 random lists:

# Lower bound, upper bound and the first-true search they are both made of: a traced run on a list with repeats,
# then a check against Python's bisect module on 2,000 random lists.
import bisect
import random


def first_true(lo, hi, test, trace=False):
    """The smallest i in [lo, hi) with test(i) true, or hi when there is none.
    test must be false on a prefix of [lo, hi) and true on the rest."""
    while lo < hi:                      # invariant: test is false before lo and true from hi on
        mid = lo + (hi - lo) // 2
        if trace:
            print(f"  lo={lo} hi={hi} mid={mid} test(mid)={test(mid)}")
        if test(mid):
            hi = mid                    # mid may be the answer: keep it
        else:
            lo = mid + 1                # mid and everything before it are false
    return lo


def lower_bound(a, x, trace=False):
    """The first position whose value is at least x (len(a) when there is none)."""
    return first_true(0, len(a), lambda i: a[i] >= x, trace)


def upper_bound(a, x):
    """The first position whose value is greater than x (len(a) when there is none)."""
    return first_true(0, len(a), lambda i: a[i] > x)


a = [12, 15, 15, 15, 18, 21, 21, 30]
print("a =", a)
print("lower bound of 15, probe by probe:")
lower_bound(a, 15, trace=True)
for x in (15, 21, 20, 10, 31):
    lo, hi = lower_bound(a, x), upper_bound(a, x)
    print(f"x = {x}: lower bound {lo}, upper bound {hi}, copies {hi - lo}")

rng = random.Random(5)
for _ in range(2000):
    b = sorted(rng.choices(range(8), k=rng.randint(0, 12)))
    x = rng.randint(-1, 8)
    assert lower_bound(b, x) == bisect.bisect_left(b, x)
    assert upper_bound(b, x) == bisect.bisect_right(b, x)
print("2,000 random lists: lower_bound == bisect_left and upper_bound == bisect_right every time")

a = [12, 15, 15, 15, 18, 21, 21, 30]
lower bound of 15, probe by probe:
  lo=0 hi=8 mid=4 test(mid)=True
  lo=0 hi=4 mid=2 test(mid)=True
  lo=0 hi=2 mid=1 test(mid)=True
  lo=0 hi=1 mid=0 test(mid)=False
x = 15: lower bound 1, upper bound 4, copies 3
x = 21: lower bound 5, upper bound 7, copies 2
x = 20: lower bound 5, upper bound 5, copies 0
x = 10: lower bound 0, upper bound 0, copies 0
x = 31: lower bound 8, upper bound 8, copies 0
2,000 random lists: lower_bound == bisect_left and upper_bound == bisect_right every time

The search does not stop at the first 15 it sees: a true test only moves hi left, until the position before it is known to be false. For 15 the bounds are 1 and 4, so the copies are at positions 1 to 3; for 20 both bounds are 5, the position 20 would take.

Counting a range with two bounds

How many of a million sorted exam marks lie between 60 and 75? The marks from 60 on start at the lower bound of 60, and the marks above 75 start at the upper bound of 75, so the answer is the difference. A key function that counts its own calls shows how much of the list each call reads:

# How many of 1,000,000 sorted exam marks lie in [60, 75]? Two bisect calls answer it. A key function that counts
# its calls shows how many marks each call read (bisect applies the key to the list's values, never to x).
import bisect
import random

rng = random.Random(11)
marks = sorted(min(100, max(0, round(rng.gauss(58, 15)))) for _ in range(1_000_000))

reads = 0


def seen(mark):
    global reads
    reads += 1
    return mark


left = bisect.bisect_left(marks, 60, key=seen)    # first mark >= 60
left_reads, reads = reads, 0
right = bisect.bisect_right(marks, 75, key=seen)  # first mark > 75
right_reads = reads

print(f"marks from 60 to 75: {right - left:,} of {len(marks):,}")
print(f"bisect_left read {left_reads} marks, bisect_right read {right_reads}")
print(f"below 60: {left:,}; above 75: {len(marks) - right:,}")
print(f"a scan agrees: {sum(60 <= m <= 75 for m in marks):,}, after reading all {len(marks):,}")

marks from 60 to 75: 339,241 of 1,000,000
bisect_left read 20 marks, bisect_right read 20
below 60: 538,745; above 75: 122,014
a scan agrees: 339,241, after reading all 1,000,000

Each call read 20 marks, and the scan that confirms the answer read all 1,000,000. The two bounds also give the marks below 60 and above 75 without another read.

The same bounds in other languages

Most languages ship these searches under different names and with different promises:

• Java’s Arrays.binarySearch returns the position of some copy, not necessarily the first, or a negative number that encodes the insertion point.
• C++ has std::lower_bound and std::upper_bound, which return iterators, and std::equal_range, which returns both bounds at once.
• Go’s slices.BinarySearch returns the lower bound and whether the value was found.
• Go’s sort.Search is the first-true search itself, over positions 0 to n − 1.
• JavaScript has no binary search in its standard library.

The first-true search proved, and the bounds in four more languages Pro: opens with a Pro, Premium or Ultimate pass

First-true search beyond arrays, with five slips drilled Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• The lower bound is the first position with a[i] >= x, the upper bound the first with a[i] > x; the copies of x sit between them and their count is the difference.
• Both are one first-true search on [lo, hi): keep mid with hi = mid when the test is true, skip it with lo = mid + 1 when it is false, and return lo.
• For a missing x both bounds give its insertion point, which may be n.
• A range count is two bounds and a subtraction: 40 reads instead of a million.