First, last and count with bounds

In a sorted list, every copy of a value sits next to the others, so two binary searches describe all of them. The lower bound of x is where the copies start: the first position whose value is at least x. The upper bound of x is where they stop: the first position whose value is greater than x. The first copy is at the lower bound, the last copy just before the upper bound, and their number is the difference of the two. A range of values works the same way: the values from a to b fill the positions from the lower bound of a up to the upper bound of b. Each question then costs two searches of about log₂ n steps, however many copies there are, where a scan reads all n values. To count with bounds, subtract two positions. This lesson states an original problem with up to 100,000 such questions, measures the scan that is too slow for it, and works through the two bounds on an example.

The problem: questions about a sorted log

Three examples on the log [61, 61, 62, 64, 64, 64, 64, 70, 95, 95], which every version of the code in this lesson answers:

1. Second 64 gives (3, 6, 4): its four lines are lines 3 to 6.
2. Second 63 gives (−1, −1, 0): nothing happened in that second.
3. The window [62, 70] gives 6, the window [71, 94] gives 0, and the window [0, 86,399] gives all 10 lines.

The brute force: read the whole log for every question

For a second, walk the log, remember the first and the last line that match and count the matches; for a window, count the lines whose second lies between a and b. It is plainly correct, which makes it the judge for faster code, but every question reads every line, so q questions cost O(n × q): 10¹¹ line reads at the limits.

"""First line, last line and count of a second in a sorted log, by scanning every line: the brute force."""
import random
import time


def scan_second(seconds, t):
    """(first, last, count) of the lines logged in second t, or (-1, -1, 0)."""
    first, last, count = -1, -1, 0
    for i, s in enumerate(seconds):
        if s == t:
            if first == -1:
                first = i
            last = i
            count += 1
    return first, last, count


def scan_window(seconds, a, b):
    """How many lines were logged from second a to second b, both included."""
    return sum(1 for s in seconds if a <= s <= b)


log = [61, 61, 62, 64, 64, 64, 64, 70, 95, 95]
print(scan_second(log, 64), scan_second(log, 63))
print(scan_window(log, 62, 70), scan_window(log, 71, 94), scan_window(log, 0, 86_399))

# A busy day: 1,000,000 lines, one second of the day (0 to 86,399) each, sorted as a log is.
rng = random.Random(7)
day = sorted(rng.randrange(86_400) for _ in range(1_000_000))
start = time.perf_counter()
for t in (0, 43_200, 86_399):
    scan_second(day, t)
per_question = (time.perf_counter() - start) / 3
print(f"one question reads all 1,000,000 lines: about {per_question * 1000:,.0f} ms")
print(f"100,000 questions: about {per_question * 100_000 / 60:,.0f} minutes")

(3, 6, 4) (-1, -1, 0)
6 0 10
one question reads all 1,000,000 lines: about 418 ms
100,000 questions: about 697 minutes

In the recorded run one question took a few hundred milliseconds, so 100,000 questions would take many hours. Support staff want their answers while the customer is still on the phone.

What to notice

The log is sorted, so the lines of one second form a single unbroken block, and so do the lines of any window. A block is fixed by two positions, where it starts and where it stops, and both are bounds. Only those two positions need a search; the lines between them never have to be read.

Two bounds for every question

For a second t, search the log twice, with the loop of the lesson on binary search invariants:

1. lo = lower_bound(log, t), the first line whose second is t or later;
2. hi = upper_bound(log, t), the first line whose second is after t.

If lo == hi the block is empty and the answer is (−1, −1, 0). Otherwise the first line is lo, the last line is hi − 1, and the count is hi − lo. Windows count with bounds the same way: the lines of [a, b] start at lower_bound(a) and stop before upper_bound(b), so the window holds upper_bound(b) − lower_bound(a) lines.

Each bound halves the unknown part of the log at every step, so it needs at most ⌊log₂ n⌋ + 1 steps: 20 for a million lines. Two bounds per question and 100,000 questions come to at most 4 million steps, where the scans needed 10¹¹ line reads.

A worked example

The two searches for second 64 on the example log, with lo = 0 and hi = 10 at the start:

The block of second 64 is therefore lines 3 to 6, and 7 − 3 = 4 lines. Notice step 1 of the lower bound: it lands on a 64 and keeps going left, because an earlier 64 could still start the block. A search that stopped at the first 64 it met would report line 5 as the first line.

The two bounds in five languages, proved and stress-tested Pro: opens with a Pro, Premium or Ultimate pass

Library calls that look logarithmic but scan, measured Pro: opens with a Pro, Premium or Ultimate pass

A hundred thousand windows: bounds, a table or one sorted walk Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• In sorted data the copies of a value form one block: it starts at the lower bound and stops just before the upper bound.
• The first copy is at the lower bound, the last at the upper bound minus one, and their count is the difference; equal bounds mean the value is absent.
• A range [a, b] holds upper_bound(b) − lower_bound(a) values, so each question costs two searches of about log₂ n steps.
• On a million lines that is 40 steps a question, against a scan that took hundreds of milliseconds each.