Binary search finds a value in a sorted array by repeatedly halving the range that could still contain it. Instead of checking every element, you check the middle one, throw away the half that can't possibly hold your answer, and repeat. Each comparison eliminates half of what's left — that's the whole trick, and it's why an array of a billion sorted elements takes at most 30 comparisons to search.
Enter a sorted, comma-separated list of numbers and a target, then step through the search. The array will be sorted automatically if it isn't already.
The algorithm keeps two pointers, lo and hi, marking a range
that is guaranteed to contain the target if it exists anywhere in the array. That's the
invariant: at the start of every step, if the target is in the array, it's between
lo and hi. Each step checks the midpoint and either finds the
target or narrows the range while preserving that guarantee — the half discarded is
provably wrong, because the array is sorted. When lo passes hi,
the range is empty and the invariant tells you the target isn't there.
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2); // avoids (lo+hi) overflow
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1; // not found
}
Overflow. mid = (lo + hi) / 2 is the textbook formula, but
in a fixed-width integer language, lo + hi can overflow before the division
happens if the array is large enough. mid = lo + (hi - lo) / 2 gives the same
result without ever summing two large numbers. JavaScript's numbers don't overflow this way
in practice, but the habit is worth keeping if you write this in C, Java, or Go.
The array must actually be sorted. Binary search doesn't check this —
it just trusts the invariant. Run it on unsorted data and it will silently return wrong
answers or a false "not found," never an error. Measured directly: running the reference
implementation above on 200,000 randomly shuffled arrays, each searching for a value that's
genuinely present somewhere in the array, it fails to find it — silently returning
-1 as if the value didn't exist — in 73.4% of trials. The
failure rate is that high specifically because shuffling destroys the one thing the
algorithm depends on; it isn't a rare edge case, it's the ordinary outcome of feeding this
function data it was never allowed to assume.
Off-by-one bounds. The loop condition lo <= hi (not
<) and the updates mid + 1 / mid - 1 (not
mid) are load-bearing. Get either wrong and the search either misses the last
valid element or loops forever on a two-element range. Measured one specific instance of
this directly: change only hi = mid - 1 to hi = mid and run it
against 200,000 random sorted arrays with a target present about half the time. It never
once returns a wrong index — either it finds the right answer or it hangs forever, and it
hangs in 31.6% of trials. The bug only bites at the very end, when the
range has narrowed to exactly two elements and the target turns out to be smaller than the
lower one: mid lands on lo, the buggy line resets hi
right back to that same lo, and neither pointer ever moves again. Worth
remembering as a general shape, not just for this algorithm: a broken boundary condition
doesn't have to mean wrong answers — it can just as easily mean the loop that's supposed to
end never does.
The opening paragraph above claims a billion-element sorted array takes at most 30
comparisons. That number means more measured directly against the one other Searching entry that assumes nothing about the data at all: linear search, which has to check every element in the
worst case. This race runs this page's own binarySearch next to linear search's own
reference loop, both searching a real sorted array of 0..n-1 for the value
n — one past the largest element, guaranteed absent, the worst case for both.
At n = 1,000,000, binary search needs 20 comparisons; linear search needs
all 1,000,000 — a 50,000x difference. That gap isn't fixed: at
n = 1,000 it's 100x (10 vs. 1,000), and at n = 100,000 it's
5,882x (17 vs. 100,000) — widening because binary search's cost grows with
log₂n while linear search's grows with n itself. Extending the same
math to the billion-element case from the opening paragraph (not re-run live here — a
billion-element array is too large to build on a button click): linear search would need up to a
billion comparisons where binary search needs 30, a roughly 33.3 million-fold
difference.
Each step halves the search range, so the number of steps to shrink an array of size
n down to one element is log₂(n). That's O(log n)
time and O(1) extra space for the iterative version above. The tradeoff is
the precondition: keeping data sorted costs something (an O(n log n) sort up front, or
O(n) insert cost to keep it sorted incrementally) — binary search is a great deal only when
you search a lot more often than you modify the data. A binary search tree keeps the same halving
idea but frees it from the array, trading that O(n) insert cost away at the cost of two
pointers per node — a cost Same Big-O,
Different Speed measures directly against this page's own reference implementation:
near-identical step counts against a balanced tree at every size, but a real, widening
wall-clock gap once the array's single contiguous block stops being the thing being compared
against scattered heap-allocated nodes. The halving idea itself isn't limited to searching for an exact value, either
— Longest Increasing Subsequence's
fastest approach reuses this exact narrowing to find a boundary instead of a match. Halving isn't
the only way to pick where to probe, either — interpolation search uses the values themselves
to guess a smarter starting point than the midpoint, at the cost of a guarantee that no longer
holds regardless of how the data happens to be distributed. Splitting into three instead of two
doesn't help either — ternary search needs
strictly more comparisons than binary search to find an exact value here, not fewer, because
it's built to answer a different question (where a unimodal sequence peaks) rather than this
one. See Choosing a Search Algorithm for how
all twelve Searching entries stack up side by side. That halving trick has one real precondition,
though — the array has to be sorted the whole way through. A sorted array that's been
rotated at an unknown pivot breaks it silently; Search in Rotated Sorted Array keeps the
same O(log n) bound by spending one extra comparison per step figuring out which half is still
genuinely sorted.