Binary Search
Binary Search
Definition: An efficient search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.
How It Works
Binary search maintains a low and high boundary over the sorted array and repeatedly checks the middle element:
low = 0, high = n - 1
while low <= high:
mid = low + (high - low) / 2
if arr[mid] == target: return mid
elif arr[mid] < target: low = mid + 1 # discard left half
else: high = mid - 1 # discard right half
return -1 # not foundEach iteration eliminates half of the remaining candidates, which is why the number of comparisons needed is bounded by log2(n): starting from n elements, after k halvings only n / 2^k elements remain, and the loop ends once that reaches 1.
The algorithm generalizes beyond exact-match lookup into “find the first/last position satisfying a predicate,” sometimes called binary search on the answer. This variant powers lower_bound/upper_bound in C++‘s <algorithm> and bisect_left/bisect_right in Python’s bisect module, and extends to problems where the search space isn’t a literal array but any monotonic function of a candidate answer (e.g. “smallest capacity that lets all packages ship within D days”).
Binary search fundamentally requires O(1) random access to be efficient. Running it over a Linked List loses the entire benefit, because just reaching the middle element takes O(n) pointer hops, making the whole search O(n) regardless of the halving logic on top.
Complexity Analysis
| Case | Time | Space |
|---|---|---|
| Best case (target is the middle element) | O(1) | O(1) |
| Average / Worst case | O(log n) | O(1) iterative, O(log n) recursive |
The recursive variant’s O(log n) space comes from call stack frames, one per halving; the iterative variant avoids that entirely by tracking low/high in local variables across loop iterations.
Why It Matters
- Reduces search operations dramatically: searching 1 million sorted items takes at most 20 comparisons instead of up to 1,000,000 for a linear scan.
- The “binary search on the answer” pattern extends far beyond arrays: it finds optimal thresholds in optimization problems (minimum capacity, maximum feasible value) whenever the search space is monotonic, a pattern that shows up constantly in competitive programming and resource-allocation problems.
git bisectapplies the same divide-and-conquer idea to source control: it finds the exact commit that introduced a regression in O(log n) test runs instead of a linear commit-by-commit search, turning a 1,000-commit history into roughly 10 test runs.
Common Pitfalls
- Applying binary search on an unsorted array yields incorrect, silently-wrong results rather than an obvious error, since the halving logic assumes sortedness to safely discard half the data.
- Integer overflow when computing
mid = (low + high) / 2, sincelow + highcan exceed the integer range on large arrays;mid = low + (high - low) / 2avoids the overflow entirely. This exact bug shipped in the JDK’sArrays.binarySearchimplementation for years before being fixed. - Off-by-one errors in loop bounds (
low <= highvslow < high) cause infinite loops or missed edge elements; always verify termination behavior on a 1-element and 0-element array before trusting the implementation. - Forgetting that duplicate values require extra logic to consistently find the first or last occurrence, rather than an arbitrary match somewhere in the middle of a run of equal values.
- Mixing up which half to discard when the comparison direction is inverted (searching a descending-sorted array with ascending-search logic), producing a search that terminates but returns wrong results.
Comparison
| Binary Search | Linear Search | Hash Table Lookup | BST Search | |
|---|---|---|---|---|
| Time complexity | O(log n) | O(n) | O(1) average | O(log n) average |
| Requires sorted data | Yes | No | No | Requires the tree property |
| Requires random access | Yes | No | No (hash-based) | No (pointer-based) |
| Extra memory needed | None | None | O(n) for the table | O(n) for the tree |
| Works on a moving/streaming dataset | Poorly, resort needed | Yes | Yes | Yes, self-balances |
| Supports “find nearest/first greater” | Yes, naturally | No, needs a full scan | No | Yes, naturally |
Example
Looking up a word in a dictionary, or git bisect binary-searching a commit history to isolate a regression, both apply this pattern. Searching for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (10 elements):
low=0 high=9 mid=4 arr[4]=16 < 23 -> low=5
low=5 high=9 mid=7 arr[7]=56 > 23 -> high=6
low=5 high=6 mid=5 arr[5]=23 == 23 -> found at index 5Three comparisons instead of scanning up to 10 elements.
Binary Search on the Answer, Traced
Given packages with weights [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] that must ship within D = 5 days, find the minimum daily shipping capacity. The search space is capacities from 1 (too small) to 55 (all packages in one day), and “can this capacity finish within 5 days” is a monotonic predicate: if capacity c works, any capacity greater than c also works.
low=1 high=55 mid=28 -> feasible in 2 days (<=5) -> search lower half, high=27
low=1 high=27 mid=14 -> feasible in 4 days (<=5) -> search lower half, high=13
low=1 high=13 mid=7 -> feasible in 6 days (>5) -> search upper half, low=8
low=8 high=13 mid=10 -> feasible in 5 days (<=5) -> search lower half, high=9
low=8 high=9 mid=8 -> feasible in 6 days (>5) -> search upper half, low=9
low=9 high=9 mid=9 -> feasible in 5 days (<=5) -> answer is 9Each mid check runs an O(n) greedy feasibility scan (simulate loading packages day by day at that capacity), and the outer binary search narrows the capacity range in O(log(max_capacity)) steps, for a total of O(n log(max_capacity)) instead of testing every candidate capacity individually.
Variants
Rotated Array Search, Traced
Searching for 6 in the rotated sorted array [15, 18, 2, 3, 6, 12]:
low=0 high=5 mid=2 arr[2]=2
left half [15,18,2] is not sorted (arr[0]=15 > arr[2]=2) -> right half [2,3,6,12] must be sorted
is 6 in sorted right half's range [3,12]? yes -> low=3
low=3 high=5 mid=4 arr[4]=6 == 6 -> found at index 4At each step, at least one half is guaranteed properly sorted (since only one rotation point exists in the whole array); checking which half is sorted, then checking whether the target falls in that half’s range, is what lets the algorithm safely discard the other half.
- Lower bound /
bisect_left: finds the first index where the target could be inserted while keeping the array sorted, i.e. the first position not less than the target. Used to find the first occurrence of a duplicate value. - Upper bound /
bisect_right: finds the last such index, i.e. the first position strictly greater than the target. Used to find the count of a value (upper_bound - lower_bound) or the insertion point after all equal elements. - Rotated sorted array search: a common interview variant where the array was sorted then rotated at an unknown pivot (e.g.
[15,18,2,3,6,12]). At each step, one half is still guaranteed to be properly sorted; check which half that is, and only apply the standard binary-search discard logic to that half. - Search in an infinite/unbounded array: when the array’s length is unknown, first find a valid upper bound by doubling a candidate index (1, 2, 4, 8, …) until it overshoots the target, then binary search normally within that bound. This is O(log p) where p is the target’s actual position, not O(log n) since n isn’t known.
FAQ
Why does binary search need low <= high instead of low < high? low <= high correctly handles the case where exactly one element remains to check (low == high); low < high would skip checking it and could report “not found” incorrectly. The right choice also depends on whether mid is included or excluded when narrowing bounds, so both variants exist and must be reasoned about together.
Can binary search be used on unsorted data at all? Only if there’s some other exploitable monotonic structure, e.g. searching for a peak element in a bitonic array. On genuinely unordered data with no structure, no divide-and-conquer strategy can safely discard half the candidates, so linear search is unavoidable.
Real-World Systems
git bisectbinary-searches commit history to isolate the exact commit that introduced a regression, treating “does this commit have the bug” as the monotonic predicate.- Python’s
bisectmodule and C++‘s<algorithm>header (lower_bound,upper_bound,binary_search) expose binary search as a standard library primitive rather than something developers hand-roll. - Database index lookups on a B+ Tree effectively perform a multi-way generalization of binary search at each node, narrowing the search range at every level of the tree rather than every array access.
- DNS resolvers and routers performing longest-prefix matching on sorted routing tables use binary-search-like narrowing as part of their lookup path, alongside trie-based structures for the full match.
Related Terms
Referenced by