Binary Search: The Primitive Under Every Index

After this lesson you can find a value in a sorted list in about log2(n) steps, count how many values fall in a range without scanning, and print the exact sequence of positions your search looked at. Every B-tree node you build in the next lessons uses this routine to choose where to go next.

Halving

If data is sorted, one comparison discards half of it. Look at the middle element: if it is too small, everything to its left is too small as well; if it is not too small, the answer is at the middle or to its left.

Step through it below, then use Unsort the array and run the same search again. The algorithm halves just as confidently and throws away the half holding your target. Sorted is a precondition, not a suggestion.

One routine: lower bound

Almost everything useful is a variation of lower bound: the position of the first element that is not smaller than x (or the length of the list if there is none). Work on a half-open range [lo, hi), starting as [0, n):

• everything left of lo is known to be smaller than x
• everything from hi on is known to be not smaller than x
• while the range is not empty, look at the middle, which is lo plus half of hi - lo, rounded down. If that element is smaller than x, lo moves to just after it. Otherwise hi moves to it.
• when lo meets hi the range is empty and lo is the answer

Worked trace for target 89 in the 12 values above:

The positions looked at (6, 9, 8) are what the PROBES command prints. The half-open range avoids the classic off-by-one bugs of closed ranges: no -1 adjustments, no special case for a single element, and the loop ends exactly when the range is empty. Computing the middle as lo plus half the gap rather than (lo + hi) / 2 avoids an overflow that real fixed-width integers hit on very large arrays.

The other operations

• Upper bound: the first element greater than x. Same loop, except that elements equal to x also count as "too small".
• Find: take the lower bound i. The value is present only if position i exists and holds x. Because lower bound lands on the first candidate, a list with duplicates answers with the leftmost match, which is what an index wants.
• Range [low, high]: the first position not smaller than low and the first position greater than high bracket the answer. Two searches cost about 2 log n, and then you read k values: O(log n + k) instead of a scan of all n. A B-tree range query does exactly this.

For 1,2,2,2,2,3: lower bound of 2 is 1, upper bound of 2 is 5, so the 2s occupy positions 1 to 4.

Commands

Input is one command per line; the list is comma-separated and sorted ascending (- means empty).

Errors: unknown command ERR unknown command: <word>, wrong argument count ERR usage: <form>, a non-integer ERR bad number: <text> (<empty> for an empty element), a list that is not ascending ERR array is not sorted.

Common mistakes

• Returning any match. With duplicates, BSEARCH must return the leftmost.
• A closed range with lo < hi. It drops the last candidate; use the half-open form.
• Probing the wrong middle. PROBES is checked exactly, so round down.
• Scanning for the range. Two binary searches, not a loop over all values.

Your exercise

The starter reads and validates the commands. You write lower_bound (recording each probe), upper_bound, find and in_range. The one mistake to avoid: shrinking the range in a way that skips the element at the middle.