Binary search is the algorithm that turns "check every element" into "discard half the problem at each step." It is elegant, fast, and widely misunderstood in its boundary conditions. Once you internalise the invariant — at every iteration, the answer is always within [lo, hi] — the off-by-one errors that plague implementations disappear.
What changed in 2026
git bisect is now AI-assisted in GitHub Copilot Workspace. The core algorithm is still binary search on commit history; the LLM identifies which test to run at each midpoint.- Database query planners teach binary search thinking. PostgreSQL 16+ EXPLAIN output now labels index scans explicitly as "binary search on B-tree," making the connection between the algorithm and index usage more visible to developers.
- Python 3.13's
bisect module added type stubs. bisect_left and bisect_right are now fully typed and work with @total_ordering objects out of the box.
- Interview culture shifted toward application problems. Coding interviews increasingly ask "where else does binary search apply?" rather than just "implement it." Knowing the real-world use cases matters.
How binary search works
Given a sorted array, find a target value. Maintain two pointers: lo (inclusive lower bound) and hi (inclusive upper bound). Check the midpoint. If the midpoint matches, return it. If target is smaller, move hi left. If target is larger, move lo right.
def binary_search(arr: list[int], target: int) -> int:
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2 # avoids integer overflow in other languages
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1 # not found
Each iteration halves the search space. For n = 1 000 000 000, the loop runs at most ⌈log₂(10⁹)⌉ = 30 iterations.
The off-by-one invariant
The most common mistake is an incorrect loop condition or boundary update. Stick to one mental model:
Inclusive bounds (lo <= hi):
lo and hi are both valid candidate indices.- When shrinking, use
lo = mid + 1 and hi = mid - 1 (exclude mid from next range).
- Loop exits when
lo > hi — empty range.
# Correct: inclusive bounds
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
...
lo = mid + 1 # NOT mid (infinite loop if arr[mid] < target)
hi = mid - 1 # NOT mid
Exclusive upper bound (lo < hi):
hi is one past the last valid index.- When shrinking:
lo = mid + 1, hi = mid (keep mid in range, exclude it from left half).
- Loop exits when
lo == hi — one element remains.
Pick one style and be consistent. Mixing them is how bugs happen.
Lower bound and upper bound
Often you want not just "does the target exist?" but "where is the leftmost (or rightmost) occurrence?"
import bisect
arr = [1, 2, 2, 2, 3, 4]
target = 2
# Leftmost position where target can be inserted to keep order
left = bisect.bisect_left(arr, target) # → 1
# Rightmost position (just after the last occurrence)
right = bisect.bisect_right(arr, target) # → 4
# All occurrences of target
occurrences = arr[left:right] # [2, 2, 2]
bisect_left is equivalent to "lower bound" in C++ STL; bisect_right is "upper bound."
Real-world applications
| Use case |
How binary search applies |
| Database B-tree index |
Each node lookup is a binary search on the sorted keys in that page |
git bisect |
Binary search on commit history to find the first bad commit |
| Package version resolution |
Binary search on sorted version list to find compatible range |
| Percentile computation |
Binary search on sorted sample to find the p95/p99 value |
| Rate limiter threshold |
Binary search to find the max request rate within a budget |
| Numerical root finding |
Bisection method: binary search on a continuous function |
Time and space complexity
| Variant |
Time |
Space |
| Classic binary search |
O(log n) |
O(1) |
| Recursive binary search |
O(log n) |
O(log n) — call stack |
bisect_left / bisect_right |
O(log n) |
O(1) |
Always prefer the iterative version: same complexity, no stack overhead, no risk of stack overflow on large arrays.
How to pick the right variant
- Simple existence check? → Classic binary search or
bisect_left + index check.
- First position to insert without disrupting order? →
bisect_left.
- Count occurrences of a value? →
bisect_right(arr, x) - bisect_left(arr, x).
- First element ≥ target? →
bisect_left → the index at that position.
- Non-trivial comparator? → Implement your own with the inclusive-bounds template.
Common mistakes
Not verifying the array is sorted. Binary search on unsorted data returns garbage. If the source is not guaranteed sorted, sort it first or use a hash set.
Using / instead of // in Python. (lo + hi) / 2 returns a float; array indices must be integers. Use //.
Integer overflow in mid calculation. In Java, C, or C++, (lo + hi) / 2 overflows when both are near Integer.MAX_VALUE. Use lo + (hi - lo) / 2.
Infinite loop from wrong boundary update. If lo = mid (not mid + 1) and arr[mid] < target, the loop never terminates. Always exclude the current mid from the next range.
What to skip
- Recursive binary search in Python for large arrays — Python's recursion limit is 1 000 by default; an array of 2^1000 elements would exceed it (theoretical, but use iteration anyway).
- Binary search on a linked list — no random access means O(n) to reach the midpoint; use a sorted array or skip list. See Linked lists explained in 2026.
- Hand-rolling binary search when
bisect / Arrays.binarySearch / std::lower_bound exists — standard library versions are tested and correct.
FAQ
How many iterations does binary search need for n = 1 billion?
At most ⌈log₂(10⁹)⌉ = 30 iterations. This is why database indexes on billion-row tables still respond in milliseconds.
Can binary search find elements in a 2D matrix?
Yes, if the matrix is sorted row-by-row with each row starting after the last element of the previous row. Treat it as a flat array: row = mid // cols, col = mid % cols.
What is exponential search?
A variant that first finds the range [2^k, 2^(k+1)] containing the target (doubling the range each step), then binary searches within it. Useful when the array size is unknown.
Is binary search always O(log n)?
For a uniformly distributed array, interpolation search is O(log log n) on average. Binary search is O(log n) regardless of value distribution.
Where to go next