--- title: 'Binary Search' source: 'https://academia.sh/en/courses/algorithms/binary-search' course: Algorithms language: en updated: '2026-08-17T18:07:40+00:00' license: 'CC BY-SA 4.0' --- # Binary Search Halving in sorted data, boundary conditions justified by a loop invariant, variants that find the first position, and search over a monotone predicate. Linear search was optimal for unordered data. If the assumption changes, the bound changes too: if the array is sorted, a single comparison eliminates not one element but **half** of the remaining ones. This lesson works through that idea. The idea is simple; writing it correctly is not — binary search is known for having carried bugs in published implementations for decades. ## The Range Invariant The algorithm keeps a range where the target can be found, and halves that range on every iteration. The way to avoid boundary errors is to write down the meaning of the range from the very start. This lesson uses a **closed range**: both bounds of `[low, high]` are included in the range. ```python def binary_search(array: list[int], target: int) -> int: """A position of the target in the sorted array; -1 if not found. Invariant: if the target is in the array, it is within [low, high]. Termination: high - low decreases by at least one every iteration. """ low, high = 0, len(array) - 1 while low <= high: mid = low + (high - low) // 2 if array[mid] == target: return mid if array[mid] < target: low = mid + 1 else: high = mid - 1 return -1 sorted_array = [1, 3, 4, 7, 9, 11, 15, 20] print(binary_search(sorted_array, 9)) # 4 print(binary_search(sorted_array, 1)) # 0 print(binary_search(sorted_array, 20)) # 7 print(binary_search(sorted_array, 10)) # -1 ``` Three details carry the correctness of the implementation: **The loop condition `low <= high`.** Because the range is closed, a single-element range is also valid; writing `<` would leave the last element never tested. **Updating the bounds with `mid ± 1`.** The tested element is left outside the range. Writing `high = mid` may leave the range unshrunk and put the loop into an infinite state — the termination guarantee comes precisely from this step. **Computing the midpoint as `low + (high - low) // 2`.** Writing `(low + high) // 2` can overflow for large arrays in languages that use fixed-width integers. The overflow behavior from the How Computers Work course turns into a concrete bug here. ## Cost Every iteration halves the range and does constant work: $$ T(n) = T(n/2) + O(1) \implies T(n) = O(\log n) $$ The number of comparisons in the worst case is $\lfloor \log_2 n \rfloor + 1$. ```python from collections.abc import Sequence def counted_binary_search(array: Sequence[int], target: int) -> tuple[int, int]: low, high, count = 0, len(array) - 1, 0 while low <= high: mid = low + (high - low) // 2 count += 1 if array[mid] == target: return mid, count if array[mid] < target: low = mid + 1 else: high = mid - 1 return -1, count for n in (1_000, 1_000_000, 1_000_000_000): # range is indexable, so a billion-element array is tested without allocating memory even_numbers = range(0, 2 * n, 2) print(n, counted_binary_search(even_numbers, n + 1)[1]) # an odd number: not in the array # 1000 10 # 1000000 20 # 1000000000 30 ``` Thirty comparisons are enough for a billion-element array. Linear search does the same work with a billion comparisons — this is the concrete counterpart of the scale-growth table in the Reading Complexity Classes lesson. The space cost is $O(1)$. The same algorithm can also be written recursively, but in that case it uses $O(\log n)$ stack space. ## Lower Bound: Why Nothing Faster Exists Comparison-based search produces one of three outcomes at every step: less, equal, greater. If the algorithm's behavior is drawn as a decision tree, every leaf of the tree is a possible answer, and an array of $n$ elements has at least $n$ different answers. A binary tree of height $h$ can have at most $2^h$ leaves. From $2^h \geq n$ it follows that $h \geq \log_2 n$: comparison-based search is $\Omega(\log n)$. The same decision-tree idea will be reused for sorting's lower bound. ## First and Last Position If the array has repeated values, the implementation above returns **any** match. Many sorting-related operations, however, want the first match. The **lower bound** is the position of the first element not less than the target. If there is no match, it gives the position where the target could be inserted without breaking the order. ```python def lower_bound(array: list[int], target: int) -> int: """The smallest i satisfying array[i] >= target (len(array) if none). Invariant: the answer is within [low, high]; the range is kept half-open. """ low, high = 0, len(array) while low < high: mid = low + (high - low) // 2 if array[mid] < target: low = mid + 1 else: high = mid return low repeated = [1, 3, 3, 3, 7, 9, 9] print(lower_bound(repeated, 3)) # 1 — first 3 print(lower_bound(repeated, 9)) # 5 — first 9 print(lower_bound(repeated, 4)) # 4 — insertion point print(lower_bound(repeated, 10)) # 7 — end of the array ``` This variant uses a **half-open** range: `high` is not included in the range. This is why the loop condition is `low < high` and the update is `high = mid`. Mixing the two variants is the most common source of bugs in binary search — how the range is kept is chosen once, and every line is written accordingly. The upper bound finds the first element **greater** than the target; the difference between the two results gives how many times the target occurs in the array. ## Beyond the Sorted Array Binary search's real condition is not "the array is sorted" but something more general: the existence of a **monotone predicate**. If a condition is false up to a certain point and always true after it, that point can be found with binary search. ```python def integer_sqrt(n: int) -> int: """The largest k satisfying k*k <= n.""" low, high, answer = 0, n, 0 while low <= high: mid = low + (high - low) // 2 if mid * mid <= n: answer = mid low = mid + 1 else: high = mid - 1 return answer print(integer_sqrt(0), integer_sqrt(15), integer_sqrt(16), integer_sqrt(10**18)) # 0 3 4 1000000000 ``` There is no array here; what is being searched for is the last value at which the predicate `mid * mid <= n` stays true. Because the predicate is monotone, halving is valid. This generalization is a common design tool: problems of the form "smallest sufficient capacity" or "largest valid threshold" are solved directly with binary search over the range of candidate values. ## When Not to Use It Binary search rests on three assumptions, and it is not preferred once one of them breaks. **If sortedness does not come for free.** Sorting the array for a single search is $O(n \log n)$; linear search is $O(n)$. Sorting pays for itself only when there are many queries. **If there is no random access.** Reaching the middle element in a linked list is linear, and the logarithmic gain vanishes. The search trees from the Data Structures course fill exactly this gap. **If the data keeps changing.** Updating a sorted array on every insertion is $O(n)$; a balanced tree or a hash table is more suitable in this case. ## Summary - Binary search halves the range in sorted data; its correctness is justified by an invariant that keeps the meaning of the range fixed. - The closed and half-open range variants require different loop conditions and updates; the two must not be mixed. - Cost is $O(\log n)$, following from $T(n) = T(n/2) + O(1)$; space is $O(1)$. - The decision-tree argument shows that comparison-based search is $\Omega(\log n)$. - The lower-bound variant gives the first match or the insertion position. - The method applies to any problem that searches for the first value at which a monotone predicate becomes true. ## Next Step Binary search's condition was sortedness; so sorting itself must now be examined. The next lesson covers three basic sorting algorithms — bubble, selection, and insertion — along with their quadratic costs, their stability, and the points where they differ from one another.