A list of 1,024 values can be searched with at most eleven midpoint inspections in this implementation.
The fixture contains every even integer from 0 through 2,046, in order. A straightforward search could inspect values one after another. Binary search starts near the middle instead. If the target is smaller, every value beyond that midpoint can be excluded at once. Each answer earns the right to discard a large portion of the remaining uncertainty.
Order turns one comparison into information about many items.
Sorted order does the heavy lifting
The program begins with an inclusive low and high index. At each step it inspects the middle item. If that value equals the target, it returns the index. If it is too small, the search continues strictly to the right; if too large, strictly to the left. The midpoint itself is removed from further consideration.
This works because the list is sorted according to the same comparison rule used by the search. Without that condition, a value larger than the target would tell us nothing reliable about the rest of its side. The algorithm’s essential promise is that any still-possible match remains inside the active interval.
What eleven questions means
The script searched separately for all 1,024 present keys and checked every returned index. The maximum was eleven midpoint probes, and the average across those equally weighted targets was about 9.012. Some targets are found immediately at a midpoint; others sit near the deepest end of the decision process.
A probe here means reading and examining one midpoint value. It is not a count of every Python comparison instruction, memory access or unit of elapsed time. The implementation may test equality and then ordering during a single probe. That definition lets the article discuss search depth without quietly turning the result into a performance benchmark.
Doubling adds roughly one level
After a midpoint rules out half the remaining values, the next question faces a smaller list. Repeating this process gives logarithmic growth in the number of probes. In the tested powers-of-two fixtures, the worst successful search rises from two probes at two items to thirteen at 4,096 items. Each doubling adds one to that measured maximum.
The boundary conventions matter for exact counts. This inclusive-index implementation is allowed an extra final inspection in some paths, so “1,024 means exactly ten comparisons” would be an inaccurate headline. The broad growth idea survives those details, while the actual program supplies the precise numbers used in the figure.
Proving that no value remains
Search is not complete unless absence is handled. The fixture also asks for −1, 1 and 2,048, none of which is present. The first two searches take ten probes and the last takes eleven. Once the low index exceeds the high index, the candidate interval is empty and the program returns a designated not-found result.
An empty input needs zero midpoint probes. These small boundary cases matter because an otherwise elegant algorithm can loop forever or read outside the list if it fails to shrink the interval correctly. Duplicate keys introduce a separate choice: any matching position, the first, the last or an insertion boundary. Our fixture uses distinct keys and does not resolve every duplicate policy.
Fast lookup has a precondition to pay for
Sorting an unordered collection costs work, so binary search is not automatically a saving for a single one-off question. Repeated lookups can make maintained order valuable, while insertions into a plain array may require shifting many items. Python’s bisect documentation separates its quick boundary search from the more expensive insertion step.
Direct access to the midpoint also matters. A linked structure that must walk through nodes to reach a position does not inherit the same overall cost just by copying the search logic. The lesson is about organizing information: when a structure supports a reliable exclusion rule and cheap access, a question about one item can eliminate many others.
Further reading
Python: bisect and insertion complexity ↗Princeton: binary search implementation ↗Original documentation and useful background.