What binary search is
Binary search is an algorithm for finding a value in sorted data by repeatedly checking the middle and throwing away the half that cannot contain the target. Each guess deletes half of what's left — the high-low guessing game, formalized.
In this lesson you'll learn the three-line loop that drives it, the bound-update rules that prevent infinite loops, and the boundary variant behind a family of classics.
Where it matters: you have a sorted list of a million values and keep being asked "is
9 in here, and where?" — thousands of times a second. Ignoring the order and walking every value costs up to a million checks per lookup — yet the sortedness already tells you where 9 can and can't be. The rule at each middle value:- if it is your target — done
- if the target is bigger, it can only be in the right half — throw the left half away
- if it's smaller, throw the right half away
The one requirement is that the data is sorted (or some yes/no condition about it flips from false to true exactly once). Before any code, let's play the game this rule comes from.
1
3
5
7
9
11
13
Quick check
arr[mid] is smaller than the target. Which half survives?
Answer it in the interactive lesson to keep your progress.
Play it — the high-low guessing game
Play one round in words: I'm thinking of a number from 1 to 10 (it's 7, but you don't know that). You guess the middle — 5. "Higher." That one answer kills 1 through 5. You guess the middle of what's left — 8. "Lower." Now only 6 and 7 survive. Guess 6 — "higher" — and it must be 7.
Four guesses for ten numbers; a million numbers would take only twenty. Watch the halves fall away below. (The coded lo/mid/hi searches live in the See it step.)
This section has a step-by-step animation in the interactive lesson.
Quick check
You guess 5 and hear "higher". Of the original ten numbers, how many are still possible?
Answer it in the interactive lesson to keep your progress.
How it works, step by step
We have a sorted list and want the index of a target like
9. Instead of scanning, we'll repeatedly look at the middle value and throw away the half that can't contain the target.The steps
- Keep two bounds:
lo = 0andhi = last index. They mark the range still in play. - While
lo <= hi, look at the middle indexmid = ⌊(lo + hi) / 2⌋— the two bounds averaged, rounded down. - If
arr[mid]is the target → returnmid. - If
arr[mid]is smaller than the target, the answer must be to the right →lo = mid + 1. - If it's bigger, the answer is to the left →
hi = mid - 1. - If the range empties (
lo > hi), the target isn't here.
Why this is correct, in one sentence: the loop keeps a promise (an invariant) — if the target is in the array at all, it is always inside
[lo, hi]. Every update preserves that promise, so when the range empties the target provably isn't there.Trace it for 9 in [1, 3, 5, 7, 9, 11, 13] (lo=0, hi=6):
mid=3→ value7.9 > 7→ search right:lo=4.mid=5→ value11.9 < 11→ search left:hi=4.mid=4→ value9. Found, index 4.
Three comparisons instead of five here — and the gap explodes as the list grows, because the range halves every round:
O(log n) (from the Complexity lesson, the halving growth rate).(The See it step animates
lo and hi closing in as the discarded half fades.) (A range that ever fails to shrink is exactly the bug the next section covers.)Binary Search Implementation in JavaScript
function binarySearch(arr, target) {
let lo = 0;
let hi = arr.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1; // not found
}
console.log(binarySearch([1, 3, 5, 7, 9, 11, 13], 9)); // 4Quick check
Searching 5 in [1, 3, 5, 7, 9, 11, 13]: the first mid is 3 (value 7). Predict the next range.
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
- The list must be sorted. Binary search on unsorted data returns garbage. If you'll search often, sort once (
O(n log n)) and reapO(log n)per lookup after. - Off-by-one on the bounds. Mixing up
lo <= hivslo < hi, orhi = midvshi = mid - 1, causes infinite loops or skipped elements. Pick one template and trust it. Updating withlo = mid(no+1) is the classic infinite loop: whenloandhiare adjacent,midequalsloand the window never shrinks. - Overflow (other languages).
(lo + hi) / 2can overflow fixed-width ints;lo + (hi - lo) / 2is the safe form. (In JavaScript,>>itself coerces to 32-bit integers, soMath.floor((lo + hi) / 2)is the general-purpose way to write the midpoint.) - Duplicates. With repeated values like
[1, 3, 7, 7, 9], exact-match binary search returns some index holding a7— not necessarily the first one. Whichmidyou land on depends on the array's shape, not on which duplicate you wanted.
That last caveat is exactly what the next section fixes: a boundary search (first index at or above the target) whose bounds rule differs on purpose — on a match it does not stop, it keeps
mid as a candidate and continues left, because an equal value might not be the first one. (The See it step animates this variant.)Quick check
Updating with `lo = mid` (no +1) risks…
Answer it in the interactive lesson to keep your progress.
Take it further — the insertion point (lower bound)
Real power comes from a tiny twist: instead of an exact match, find where a value belongs — the first index whose value is
≥ target. Keep hi = length (not length - 1), and on arr[mid] < target go right, otherwise keep mid as a candidate (hi = mid, without the - 1). This one template also answers "first/last position" and "search-insert-position".Trace it: lower bound of 7 in [1, 3, 7, 7, 9]
Start with
lo = 0, hi = 5 (one past the end):| round | lo | hi | mid | arr[mid] | decision |
|---|---|---|---|---|---|
| 1 | 0 | 5 | 2 | 7 | 7 ≥ 7 — mid might be the first 7, keep it: hi = 2 |
| 2 | 0 | 2 | 1 | 3 | 3 < 7 — too small, go right: lo = 2 |
| 3 | 2 | 2 | — | — | lo === hi — the loop stops, return 2 |
Notice round 1: an exact-match search would have stopped at index 2 and gotten lucky. Lower bound doesn't trust luck — it keeps index 2 as a candidate and checks whether an earlier
7 exists to its left. Here there isn't one, so lo and hi meet at 2.Lower Bound Implementation in JavaScript
function lowerBound(arr, target) {
let lo = 0, hi = arr.length; // hi past the end
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] < target) lo = mid + 1; // answer is to the right
else hi = mid; // mid might be it
}
return lo;
}
console.log(lowerBound([1, 3, 5, 7], 6)); // 3 (6 inserts before 7)
console.log(lowerBound([1, 3, 5, 7], 5)); // 2 (first index of 5)Quick check
Lower bound of 7 in [1, 3, 7, 7, 9]. Predict the answer.
Answer it in the interactive lesson to keep your progress.
How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, halving repeatedly is the whole payoff — a million values fall to nothing in about 20 guesses, because
log₂(1,000,000) ≈ 20:| Approach on sorted data | Time | Space | 1,000,000 values |
|---|---|---|---|
| linear scan | O(n) | O(1) | up to 1,000,000 checks |
| binary search | O(log n) | O(1) | ~20 checks |
Two footnotes on that table.
O(log n) is the worst case — the best case is O(1), when the very first middle probe happens to be the target. And the O(1) space assumes the loop version from this lesson; binary search can also be written recursively (call yourself on the surviving half), but each call sits on the call stack, costing O(log n) space for no benefit here (see the Recursion lesson for when that trade is worth it).When does the sort to enable it pay off? If you search the data once, a plain
O(n) scan beats sorting. If you search it many times, sorting once (O(n log n)) amortizes and every lookup is O(log n).One practical note: most languages ship this — Python's
bisect, Java's Arrays.binarySearch, C++'s std::lower_bound. JavaScript has no built-in, which is exactly why the hand-rolled template from this lesson is worth owning.Key takeaways:
- Binary search needs a sorted (monotonic) space; each step throws away half.
O(log n)— ~20 steps for a million, ~10 for a thousand.- Pick one bounds template and trust it;
lo = midwithout+1loops forever.
The real skill is spotting a "sorted space" that isn't obviously an array. These classics each get their own lesson later (no need to know them yet): first/last position of a target (the boundary search), search in a rotated sorted array (animated in See it — each step first asks which half is still sorted before deciding where the target can hide), and binary search on the answer — guess a capacity/speed and check feasibility. Next up in order: Sorting — how the data gets ordered in the first place.