We have been promising it for three lessons: we previewed it in 01-01 as motivation, we used it in 01-03 to illustrate logarithmic growth, and Module 3 closed by calling it "the jewel of logarithmic efficiency". The time has come to pay that debt. Binary search locates an element in a sorted collection by discarding half of the candidates at every step: where find_stop (02-03) needed up to 40 comparisons to find a stop on a 40-stop line, binary search needs 6. In this lesson we will implement it with surgical care — it is famous for packing subtle bugs into four lines —, trace it over the RutaBus stop catalog, analyze it with the tools from Module 2, and connect it with its parent strategy: divide and conquer (03-01).

1. The non-negotiable requirement: a sorted collection
2. Iterative implementation with invariants
3. Step-by-step trace: finding a stop by code
4. Recursive version
5. Analysis: why O(log n)
6. Binary search versus linear search
7. Useful variants: first occurrence and the bisect module

Binary search makes a bet: it looks at the middle element and, by comparing it with the target, decides which half it cannot be in. That deduction is only valid if the collection is sorted. If the middle element is smaller than the target, everything to its left is too — and we can discard it wholesale without looking at it. Without order there is no deduction to make: discarding a half would be flipping a coin.

RutaBus's central stop catalog assigns each stop an alphabetic code. Kept in order, it is the perfect setting:

And if the list is not sorted? Sorting it has its own cost and its own algorithms — exactly the subject of the next three lessons (04-02 to 04-04). Here we take the order as given; the practical rule for when it pays to sort in order to search comes when we compare costs in section 6.

The iterative version is the canonical one. Every line has a precise justification:

The tool for reasoning about this loop is its invariant: a statement that is true before every iteration. Here it is:

If target is in the list, its index lies in the range [left, right].

Every piece of the code exists to preserve that invariant:

• middle = (left + right) // 2: the central index of the current range (integer division // rounds down when the range has even size). Choosing the center is what guarantees that, whatever we decide, we discard half of the candidates — no more, no less.
• left = middle + 1 (and not left = middle): we have already checked that items[middle] != target, so middle stops being a candidate. Skipping it does not break the invariant (the target cannot be there) and is what guarantees that the range always shrinks — the key to the loop terminating.
• right = middle - 1: the symmetric argument.
• while left <= right: the range [left, right] contains right - left + 1 elements; when left > right it contains zero. At that point the invariant says: "if it were present, it would be in an empty range" — that is, it is not present. That is why the return -1 after the loop is correct, not a patch.

Notice how reasoning by invariant turns "I'm pretty sure it works" into a proof: invariant true at the start (the whole range is a candidate), preserved on every iteration, and a strictly shrinking range → the algorithm terminates and its answer is correct.

Let's search for the code "PMA" (Main Square) in the list of 9 codes. The indices run from 0 to 8:

Three comparisons for 9 elements. Linear search would have needed 6 (it walks through AVP, ESN, HCE, MVJ, PDR, PMA). Watch the discarding mechanics: after the first comparison, 4 candidates remain; after the second, 1. Each round cuts the range in half (sometimes slightly less than half, never more).

And a failed search, "HOS" (a code that does not exist):

Four comparisons to certify absence among 9 elements. Recall from 02-03 that in linear search verifying absence forces you to look at everything (n comparisons); here log n is enough — absence is certified at the same price as presence.

The structure "discard a half and repeat" is naturally recursive, and in fact it is a degenerate case of divide and conquer: the problem is divided into two halves but only one is conquered (the other is discarded), and there is nothing to combine:

Same logic, same comparisons. The difference is in space: every pending call occupies a frame on the call stack (02-02), so the recursive version uses O(log n) of auxiliary space against the O(1) of the iterative one. Since Python does not optimize tail recursion either, in practice the iterative version is preferred; the recursive one is worth knowing as a conceptual bridge to the algorithms of 04-03 and 04-04, which genuinely need recursion.

Let's apply the halving-count method — the same level counting as in 03-01. Each failed comparison reduces the number of candidates at least by half:

The question "how many times can I divide n by 2 until reaching 1?" has had a name since 01-03: log₂ n. The worst case therefore makes ⌊log₂ n⌋ + 1 comparisons → O(log n). It is the recurrence T(n) = T(n/2) + O(1): a single subproblem of half the size plus constant work — compare it with the T(n) = 2·T(n/2) + O(n) we left pending in 03-01 and will solve in 04-03.

The three cases, using the criteria of 02-03:

• Best case — Θ(1): the target sits exactly at the first middle. One comparison.
• Worst case — Θ(log n): the target sits at a "leaf" of the halving process, or is absent.
• Average case — Θ(log n): most elements need close to log n steps (half of the elements are only reached at the last level), so the average lands within a comparison or two of the worst case.

Space: O(1) auxiliary in the iterative version (three variables), O(log n) in the recursive one because of the stack.

Let's pit the newcomer against find_stop from 02-03:

To get a physical feel for it: with the national catalog of 1,000,000 stops, linear search averages 500,000 comparisons; binary search, 20. It is the difference between hierarchies from 01-03 made flesh.

The fine print is the prerequisite. If the list changes constantly and you will search only once, sorting first (which will cost O(n log n), as we will see) to save on a single search is a bad deal: linear search wins. Binary search shines when the cost of sorting is amortized over many searches — a catalog sorted once at deployment and queried millions of times a day, like RutaBus's.

Our binary_search returns some index where the target is. If there are duplicates — several arrivals with the same time on a board — we often want the first one. The trick: on finding a match, don't stop; note it down and keep searching to the left:

It is still O(log n): we have added no rounds, only changed what we do on a hit. The invariant is now "result is the leftmost occurrence seen so far, and if there is an earlier one it lies in [left, right]".

Python ships binary search out of the box in the bisect module — in fact we already used it without explanation in record_arrival (02-03, exercise 3):

Two subtleties that confuse people at first:

• bisect_left/bisect_right do not tell you whether the element is present: they return the insertion point that keeps the order. To find out whether it is there: i = bisect_left(items, x) and check i < len(items) and items[i] == x — which is exactly first_occurrence for free.
• insort searches in O(log n) but inserts in O(n) because of the shifting done by list.insert — the conclusion of the 02-03 exercise still stands: binary search speeds up the finding, not the moving.

• Applying it to an unsorted list. The number one mistake, and the most treacherous: it raises no exception, it simply returns wrong results some of the time. If in doubt, assert items == sorted(items) during development.
• Off-by-one on the bounds. right = len(items) instead of len(items) - 1, or while left < right instead of <=: both make the last candidate never get examined (searches that "fail to find" elements sitting at the edges). Pick a convention — here, closed range [left, right] — and stay consistent with it across the three lines that depend on it.
• Infinite loop from not shrinking the range. Writing left = middle (without + 1) looks innocent, but with a 2-element range middle == left and the range no longer changes: eternal loop. The golden rule: after each round, middle must end up outside the new range.
• The overflow anecdote. For decades, the reference implementation in Java computed medio = (izq + der) / 2; in 2006 it was discovered that with arrays of more than 2³⁰ elements the sum of the two indices overflowed the 32-bit integer and produced a negative index. The classic fix is middle = left + (right - left) // 2. In Python it cannot happen — integers have arbitrary precision — but you will meet it the moment you touch Java, C or C++, and it is a reminder that even the most analyzed algorithm in history hid a bug for 60 years.
• Tip: when you doubt your implementation, systematically test the four border cases: empty list, one element (present and absent), target smaller than everything, target larger than everything. Those five tests catch nearly all off-by-one errors.

Trace by hand (table with left, right, middle, comparison and action) the search for the code "TSU" in codes = ["AVP", "ESN", "HCE", "MVJ", "PDR", "PMA", "POL", "TSU", "UNI"]. How many comparisons does it need? And linear search?

RutaBus stores the accumulated kilometers of each L1 run in a sorted list. Write count_before(kms, limit) that returns how many runs have strictly fewer than limit km, in O(log n). Hint: don't search for an element; search for a cut point — you can do it with your own binary search or with one call to bisect.

This version arrives from a RutaBus code review with two bugs. Find them and explain what symptom each one produces (wrong result? infinite loop?):

Solution 1

3 comparisons. Linear search would have made 8 (it is the next-to-last element). With just 9 elements the advantage looks modest — remember from 01-03 that the hierarchies pull apart as n grows.

Solution 2

In a sorted list, "how many are smaller than limit" is exactly the index where limit would be inserted from the left:

By hand it would be the binary search for the "first index with kms[i] >= limit". This pattern — using binary search to count instead of to find — is among the most profitable in practice. Common mistake: using bisect_right, which would also count the runs with exactly limit km (the statement asked for strictly fewer).

Solution 3

• Bug 1: right = len(items) combined with the condition left <= right. As soon as the range hugs the right edge, middle can equal len(items) and items[middle] raises IndexError (for example, searching for a target larger than every element). Fix: right = len(items) - 1.
• Bug 2: left = middle without + 1. With left = 4, right = 5, middle = 4; if items[4] < target, the assignment sets left = 4... and the state does not change: infinite loop. Fix: left = middle + 1, which is moreover correct because middle has already been ruled out.

The symptom betrays the culprit: an index exception points at the initial bounds; a hang points at a range that fails to shrink.

The debt is paid: binary search discards half of the candidates with every comparison thanks to the invariant "if it is there, it is in [left, right]", and that makes it O(log n) in the worst and average cases — against the Θ(n) of find_stop — with O(1) space in its iterative form. We have seen why every detail matters (middle + 1 to guarantee termination, left <= right so as not to lose the last candidate), the first-occurrence variant and Python's built-in bisect, and we have cataloged its historical traps, from the off-by-one to the overflow that lived for 60 years in the standard libraries. All of its power rests on a condition we have taken as a gift: that the list be sorted. And who sorts it? That is exactly the problem of the next three lessons. We will start in 04-02 with the most human algorithm of them all — the one you use without knowing it when sorting cards or straightening out an arrivals board by hand —: insertion sort.