In lesson 1, a linear search of a 100,000-item library cost 100,000 comparisons. A binary search costs 17.

There is one condition: the library must be sorted. This is the first time in the course that order is a requirement rather than a convenience — and the question of how it gets sorted is what lessons 7–9 answer.

The invariant

The search keeps two edges, lo and hi, and one rule holds throughout:

the answer is always between lo and hi.

At the start lo = 0 and hi = len(items) — one past the end. That is not a mistake: "not found" is a legal answer, and that is where it lives.

Each step takes the midpoint and throws half the range away:

  if items[mid] < target:  lo = mid + 1   // mid is too small; it cannot be the answer
  else:                    hi = mid       // mid MIGHT be the answer; it stays

The asymmetry between mid + 1 and mid is the whole thing. Almost everyone writing their first binary search gets it wrong exactly there — and ends up with an infinite loop, or an answer off by one.

What it returns

Not "did I find it", but the index of the first item that is ≥ the target. That is called at-or-after, and it is what transit does: "the next bus at or after 08:00".

An exact-match search is this plus one equality check. It does not work the other way round: from a found/not-found answer you cannot recover where the item would have been.

Guess before you read on

17 comparisons against 100,000. There seems to be nothing to argue about.

At what n does binary search start winning on the CLOCK?

Write your number down. And a second one: is that number a single value?