We closed the graphs module by saying that the next muscle to train was a different one: searching and sorting within large volumes of data. Rutalia accumulates millions of rows — the delivery history with its timestamps, the product catalog, the weight-tier rates — and on sorted data there is a tool that turns searches of millions of steps into a few dozen: binary search. You have already met it in passing: in 01-02 we analyzed its recurrence T(n) = T(n/2) + c ("search in sorted addresses") and concluded it was O(log n). This lesson works it in depth, because binary search has a well-earned reputation as the sharpest and the most treacherous of the basic techniques: it is trivial to state, yet a classic study found bugs in the majority of implementations written by professional programmers. You will learn to write it with an invariant that makes it bulletproof, its lower_bound/upper_bound variants, Python's bisect module, and the most powerful pattern of all: binary search on the answer.

1. Classic binary search and why it is treacherous
2. The interval invariant: the right way to reason
3. lower_bound and upper_bound: first and last occurrence
4. Python's bisect module in practice
5. Binary search on the answer: the "is feasible(x)?" pattern
6. Monotonic functions and a mention of ternary search

The idea is the familiar one: if the array is sorted, compare against the middle element and discard the half that cannot contain what you are looking for. Each comparison halves the problem, hence the recurrence T(n) = T(n/2) + c that we solved in 01-02: O(log n). Over a history of 10 million Rutalia deliveries, that is about 24 comparisons versus the 10,000,000 of a linear scan.

Let's break down why each line is the way it is, because this is where people get cut:

• lo, hi = 0, len(data) - 1: we choose to represent the closed interval [lo, hi] — both endpoints are valid candidates. This decision shapes everything else.
• while lo <= hi: with a closed interval, the interval is empty when lo > hi. Writing lo < hi here would be a bug: it would leave the single-candidate case unexamined.
• lo = mid + 1 and hi = mid - 1: we always exclude mid from the new interval, because we have already examined it. Writing lo = mid or hi = mid in this version produces the classic infinite loop when the interval shrinks to one or two elements and mid stops advancing.

In Python, integers have arbitrary precision and this line is safe. But it is worth knowing: in Java, C or C++, (lo + hi) / 2 with 32-bit integers overflows when lo + hi exceeds 2³¹ − 1, even though both values are valid indices on their own. This bug sat in the binary search of Java's standard library (java.util.Arrays.binarySearch) for nearly ten years until it was detected in 2006. The robust form in those languages is:

If one day you port your Rutalia code from Python to a Java or Go service, remember this line. It is the perfect example of why binary search is treacherous: the algorithm is correct on the whiteboard and fails on the machine.

In 03-03 we reasoned about Dijkstra with an invariant ("distances extracted from the heap are final"). Binary search is mastered the same way: instead of memorizing where each +1 goes, you declare an invariant and maintain it.

Let's use the semi-open convention [lo, hi), which is Python's native one (slicing, range, bisect). The invariant we choose, with the most useful variant already in mind:

Invariant: every element with index < lo is strictly less than the target; every element with index >= hi is greater than or equal to the target.

Graphically, the array is split into three zones that the loop keeps narrowing:

Notice the details and compare them with the closed version:

• Here hi = mid without -1 is correct, because hi is exclusive: assigning hi = mid means "I know data[mid] >= target", exactly what the invariant demands.
• There is no infinite loop: since lo < hi inside the loop, we always have mid < hi, so hi = mid strictly shrinks the interval, and so does lo = mid + 1.
• On exit, lo == hi and the two zones touch: lo is the boundary between "less than the target" and "greater than or equal". That boundary is a much richer result than a mere "present / absent".

This way of thinking — choose the invariant, write each branch to maintain it, and the result falls out on its own — is the one you must internalize. Every variant that follows is the same skeleton with a different invariant.

Real data has duplicates. In Rutalia's history, thousands of deliveries share the same day; in the rate table, several products share a weight tier. The useful question is almost never "is value X present?" but "where does the block of X start and where does it end?". Two boundaries exist for that:

With both boundaries you can answer everything:

• First occurrence of x: i = lower_bound(a, x); it exists if i < len(a) and a[i] == x.
• Last occurrence of x: upper_bound(a, x) - 1 (if x exists).
• Number of occurrences: upper_bound(a, x) - lower_bound(a, x) — zero if x is absent.
• Range of an interval of values [x, y]: a[lower_bound(a, x) : upper_bound(a, y)].

upper_bound is lower_bound with one comparison changed (<= instead of < when picking the branch). In Python you don't need to write them: they come ready-made.

The standard library ships both boundaries under their own names: bisect_left is lower_bound and bisect_right (alias bisect) is upper_bound. In addition, insort_left/insort_right insert while keeping the list sorted (careful: insertion into a list is O(n) because elements shift; only locating the position is logarithmic).

Let's see it on Rutalia's delivery history, sorted by timestamp. As always, generic fictional data:

Two important tricks in the example:

• Searching with partial tuples: ("2026-07-01T09:00:00",) is a one-element tuple; when compared against three-element tuples, lexicographic comparison decides on the first field, which is exactly what we want. For the upper limit we append a "very large" sentinel ("￿") as the second field, so that every delivery at that exact instant is included.
• bisect_left for the start, bisect_right for the end: the universal pattern for extracting ranges with duplicates.

Since Python 3.10, bisect accepts key=, which avoids the sentinels:

Rutalia charges shipping according to package weight, by tiers. This problem — "given a value, which tier does it fall into?" — is exactly one call to bisect:

The choice between bisect_left and bisect_right here is not cosmetic: it decides whether the exact bound (2.0 kg) falls into the cheap tier or the expensive one. With bisect_right, 2.0 kg would pay 5.50 EUR. It is the kind of boundary detail that in production translates into incorrect billing — another display of the treacherous character of this family of algorithms.

So far we were searching in an array. The big conceptual leap of this lesson is that you can search in the space of possible answers, even when no array exists. Only one property is needed:

If there is a function feasible(x) that answers yes/no and is monotonic — if x works, every x' > x also works (or the other way around) — then the optimal answer can be found by binary search on x.

The answer space looks like this: NO NO NO NO YES YES YES YES. Finding the boundary between the last NO and the first YES is exactly a lower_bound over a "virtual array" that we never materialize.

The van for zone CEN must deliver a sequence of packages in the given order (that is how they come palletized from the warehouse), in at most k trips. What is the minimum capacity (kg) the van needs?

• Is it monotonic? Yes: if capacity C can do it in k trips, so can C+1 (the big van can imitate the small one).
• feasible(C): checked with a trivial greedy — keep filling the current trip and open a new one when the package doesn't fit. Sound familiar? It is a cousin of the first-fit from the bin packing of 02-02, but here the order is fixed and the greedy actually is exact.

Analysis: each feasible costs O(n) and we make O(log R) calls, with R = sum − max; total O(n · log R). The naive alternative of trying capacities one by one is O(n · R): with weights in grams and ranges in tons, the gap is enormous.

Same pattern in a different disguise: Rutalia has m couriers and courier i takes t_i minutes per delivery (motorbike, bicycle, van...). What is the minimum time T to complete n deliveries with everyone working in parallel?

• feasible(T): in T minutes, courier i completes T // t_i deliveries. Do they add up to at least n? An O(m) computation.
• Monotonicity: more time, more deliveries. NO→YES boundary.

The mental pattern to take away: whenever the problem statement asks for "the minimum X such that..." or "the maximum X such that...", ask yourself whether you can write a monotonic, cheap feasible(x). If the answer is yes, the optimization problem turns into O(log R) decision problems. In 02-03 we searched for optima by pruning trees with bounds; here we search by narrowing an interval. Two different philosophies for the same verb: optimize.

Binary search does not need an array: it needs monotonicity. It works just as well for solving f(x) = target with f increasing and continuous (numerical bisection, with while hi - lo > 1e-9 instead of indices), for instance to calibrate the average speed the fleet must drive at to meet a delivery window.

If the function is not monotonic but is unimodal (it goes down and then up, like total cost as a function of the number of vans: too few = overtime, too many = underused fleet), the sibling tool is ternary search: evaluate two interior points m1 < m2 and discard the third that cannot contain the minimum. It is also O(log n). We won't develop it further: keep in mind that it exists, along with the keyword unimodal to recognize when to apply it.

• Mixing interval conventions. 90% of the bugs come from using hi = len(a) with while lo <= hi, or hi = len(a) - 1 with hi = mid. Pick one convention (we recommend the semi-open [lo, hi), Python's native one) and note it in a comment on the first line.
• Not checking the result of bisect_left. bisect_left(a, x) returns an insertion position; it does not guarantee that x is present: check i < len(a) and a[i] == x before declaring the element found.
• Searching in unsorted data. Binary search on an unsorted array does not fail loudly: it returns garbage with total confidence. In development, an assert all(a[i] <= a[i+1] for i in range(len(a)-1)) will save you (remove it in production: it is O(n) and defeats the whole point).
• Infinite loop in the "maximize" variant. If you search for the maximum feasible x over integers and move lo = mid, the downward rounding of (lo + hi) // 2 makes no progress when hi == lo + 1. Solution: round up with mid = (lo + hi + 1) // 2 in that variant.
• Wrong initial bounds in search on the answer. If lo is not a valid lower bound (e.g. forgetting max(weights) in the van example), the checker may run with capacities where not even a single package fits and return nonsense. Spend a minute justifying both bounds.
• Tip: when in doubt about an implementation, test it against brute force with small random arrays, including the empty one and the single-element one. Binary search almost always fails at n ∈ {0, 1, 2}.

Exercise 1 — One day's range in the history. With the history sorted by timestamp from the bisect section, write deliveries_on_day(history, day) returning the list of deliveries whose timestamp starts with day (format "2026-07-01"), using bisect_left/bisect_right (do not scan the whole list). The cost must be O(log n) + O(k), where k is the size of the result.

Exercise 2 — Last delivery before an instant. Write last_delivery_before(history, ts) returning the last delivery whose timestamp is strictly less than ts, or None if there is none. Hint: which boundary gives you that position directly, bisect_left or bisect_right?

Exercise 3 — Maximum admissible package weight. Let's flip the search-on-the-answer pattern: Rutalia wants to advertise the maximum per-package weight it can promise, knowing that its van of fixed capacity C must still complete the delivery of weights (in order) in k trips, and assuming that any package exceeding the advertised weight gets capped at that weight. Write max_allowed_weight(weights, k, C) with binary search on the answer. Watch out for the "maximize" variant and its infinite loop.

Solution 1:

The trick is the lesson's: the prefix "2026-07-01" is smaller than any timestamp of the day (because any extra character makes the longer string greater when the prefix matches), and the sentinel "￿" exceeds all of them. Cost: two O(log n) searches plus the O(k) slice.

Solution 2:

bisect_left gives the first element >= ts; the one before it is, by definition of the invariant, the last one < ts. With bisect_right we would have obtained "the last one with timestamp <= ts", the other common semantics — choosing the right boundary is the exercise.

Solution 3:

The monotonicity runs the other way this time: the lower the advertised weight, the lower the total load and the fewer the trips — if x is feasible, so is x−1. That is why the boundary is YES→NO, we move lo = mid on success, and that forces the upward rounding (lo + hi + 1) // 2 to guarantee progress.

Binary search is pure O(log n): the recurrence T(n) = T(n/2) + c from module 1 turned into a tool. The essence of this lesson is not the algorithm — it fits in ten lines — but the discipline: (1) choose an interval convention and an invariant, and let them write the branches for you; (2) think in boundaries (lower_bound/upper_bound) rather than in "present or absent", because boundaries answer ranges, counts and rate tiers; (3) recognize the search on the answer pattern: any monotonic "minimum/maximum x such that feasible(x)" is solved with O(log R) calls to a cheap checker — that is how we computed the minimum capacity of Rutalia's fleet without trying capacities one by one.

All of this rested on a silent premise: that the data was already sorted. The history by timestamp, the weight-tier rates, the catalog... someone had to sort them, and over millions of rows that is not done just any old way. In the next lesson (04-02) we open the sorting box: why O(n²) algorithms die at scale, how mergesort and quicksort achieve O(n log n), why that bound cannot be beaten by comparing... and how, with the right cards (Rutalia's postal codes, for example), it can indeed be beaten.