Binary Search Explained: Halving Your Way to O(log n)
Binary search finds a value in a sorted array by halving the search space each step. Learn the algorithm, the off-by-one traps, and real variants.
By Velloreth
The idea in one paragraph
Binary search finds a value in a sorted collection by looking at the middle element and discarding the half that cannot contain the target. Repeat until you find it or the space is empty. Because each step halves what remains, a million elements take about twenty comparisons instead of a million.
That is the entire algorithm. Everything else is implementation detail and edge cases.
The iterative implementation
function binarySearch(sorted, target) {
let low = 0;
let high = sorted.length - 1;
while (low <= high) {
const mid = low + Math.floor((high - low) / 2);
if (sorted[mid] === target) return mid;
if (sorted[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}
Four things to notice, because each is a place people get it wrong.
low <= high, not low < high. With low < high you exit the loop when the range has one element left, and you never check that element. A single-element array would always return -1.
mid + 1 and mid - 1, not mid. The midpoint has already been checked and ruled out. Keeping it in the range means the range may not shrink, and the loop can run forever.
low + (high - low) / 2. The obvious (low + high) / 2 overflows in fixed-width integer languages when both values are large. Java’s Arrays.binarySearch had exactly this bug for nine years before it was fixed in 2006. JavaScript numbers are doubles so it does not bite there, but the habit is worth forming.
Math.floor. In languages with integer division this is automatic. In JavaScript, division produces a float, and sorted[2.5] is undefined.
Why it is O(log n)
Each iteration halves the search space. Starting with n elements:
| Step | Elements remaining |
|---|---|
| 0 | 1,000,000 |
| 1 | 500,000 |
| 2 | 250,000 |
| 5 | 31,250 |
| 10 | 977 |
| 20 | 1 |
After k steps, n / 2ᵏ elements remain. The loop ends when that reaches 1, so k = log₂(n). For a million elements, that is about 20.
This is why binary search is the standard answer to “how do you find something in a huge sorted dataset”. A linear scan of a billion records takes a billion comparisons; binary search takes thirty.
The sorted requirement
Binary search assumes the data is sorted. If it is not, the algorithm does not fail loudly — it returns a wrong answer, usually -1, and you spend an afternoon debugging.
binarySearch([3, 1, 4, 1, 5], 4); // -1, even though 4 is present
The comparison sorted[mid] < target is meaningless on unsorted data, so the algorithm discards the half that actually contains the target.
This is why binary search is almost always paired with a sort. Sorting is O(n log n), so if you search once, a linear scan is cheaper. If you search many times, sorting once and binary searching each time wins.
The generalised pattern
Exact lookup is the textbook case, but the real power of binary search is that it answers any question of the form “find the boundary where a condition flips from false to true”.
Lower bound: first index where value >= target
function lowerBound(sorted, target) {
let low = 0;
let high = sorted.length;
while (low < high) {
const mid = low + Math.floor((high - low) / 2);
if (sorted[mid] < target) low = mid + 1;
else high = mid;
}
return low;
}
This returns the insertion point — where the target would go to keep the array sorted. It is what Array.prototype.findIndex cannot do efficiently, and it is the basis of bisect in Python and lower_bound in C++.
Upper bound: first index where value > target
Change the comparison to <= and you get the other boundary. Together, the two bounds give you the count of occurrences of a value in O(log n).
Binary search on the answer
The most powerful form: when a problem asks for the smallest value satisfying some monotonic condition, binary search the answer space directly.
// Smallest capacity that ships all packages within `days`
function shipWithinDays(weights, days) {
let low = Math.max(...weights);
let high = weights.reduce((a, b) => a + b, 0);
while (low < high) {
const mid = low + Math.floor((high - low) / 2);
if (canShip(weights, days, mid)) high = mid;
else low = mid + 1;
}
return low;
}
You never search an array here. You search the range of possible answers, using a predicate that is monotonic — if capacity c works, every capacity above c works. That monotonicity is the only requirement.
This technique solves a surprising range of problems: minimum time to complete tasks, smallest divisor, kth smallest element in a matrix, and many optimisation problems that look like they need dynamic programming.
Recursive form
function binarySearchRecursive(sorted, target, low = 0, high = sorted.length - 1) {
if (low > high) return -1;
const mid = low + Math.floor((high - low) / 2);
if (sorted[mid] === target) return mid;
if (sorted[mid] < target) return binarySearchRecursive(sorted, target, mid + 1, high);
return binarySearchRecursive(sorted, target, low, mid - 1);
}
The recursive form is clearer to read but uses O(log n) stack space and is slower in practice due to call overhead. Prefer the iterative version in production.
Common bugs and how to avoid them
Infinite loop. Caused by not shrinking the range. If you write low = mid instead of low = mid + 1, and the range has two elements, mid equals low and the range never shrinks.
Missing the last element. Caused by low < high when you need low <= high. The fix is to decide deliberately whether your range is inclusive or half-open, and be consistent.
Overflow. (low + high) / 2 overflows in Java, C, and Go for large arrays. Use low + (high - low) / 2.
Wrong boundary variant. Lower bound and upper bound differ by one comparison. Mixing them up gives an off-by-one result that is easy to miss in testing.
Searching unsorted data. No error, just wrong answers. Assert sortedness in tests.
When not to use binary search
Unsorted data you search once. Sorting costs O(n log n), which is worse than a single O(n) scan.
Linked lists. Reaching the middle costs O(n), so the total is O(n log n) at best — worse than a linear scan.
Small arrays. For fewer than about 20 elements, a linear scan is faster because it has no branch misprediction and no setup cost. Many standard libraries switch to linear search below a threshold.
Data that changes constantly. Every insertion into a sorted array costs O(n) to shift elements. If you insert and search in equal measure, a balanced tree or a hash map is better.
Where it shows up in practice
- Database indexes — B-trees are binary search generalised to many-way branching, which is why indexed lookups are fast.
git bisect— binary searches your commit history to find the commit that introduced a bug.- Version control and package managers — resolving version ranges uses binary search over sorted version lists.
- Autocomplete and typeahead — finding the range of completions for a prefix.
- Numerical methods — root finding by bisection is binary search on a continuous function.
- Rate limiting and capacity planning — binary searching for the smallest configuration that meets a target.
For the complexity reasoning behind these costs, see Big-O notation explained. For the structures that make sorted search possible, data structures every developer should know and trees and graphs explained. If you are practising for interviews, debugging strategies that work covers the reasoning that matters.
Quotable summary
Binary search finds a value in a sorted collection by comparing with the middle element and discarding the half that cannot contain the target, halving the search space each step for O(log n) time and O(1) space. It requires sorted input and returns wrong answers silently on unsorted data. The generalised form answers any monotonic yes/no question, which makes it applicable to boundary finding, insertion points, and optimisation problems where the answer space is searched rather than an array. The most common bugs are off-by-one errors in the loop condition and midpoint update, and integer overflow in the midpoint calculation.