What binary search is
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 is a linear O(n) scan: up to a million checks per lookup. But the sortedness already tells you where 9 can and can't be — throwing that away on every step is the waste.Binary search uses the order. It's the high-low guessing game: look at the middle value, and
- 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
Each guess deletes half of what's left. The one requirement is that the data is sorted (or some yes/no condition about it flips from false to true exactly once).
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.
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.
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). In JavaScript, one way to write those steps:In the animation, watch the
lo and hi markers close in and the discarded half fade each round. Before each step, predict two things: where mid will land, and which bound will jump. If the surviving range does not shrink after a step, something is wrong — that is exactly the bug the next section covers.This section has a step-by-step animation in the interactive lesson.
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. The animation below shows the subtle boundary variant (first index at or above the target). Watch its bounds rule: on a match it does not stop — it keepsmidas a candidate and continues left, because an equal value might not be the first one.
This section has a step-by-step animation in the interactive lesson.
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. This one template also answers "first/last position" and "search-insert-position":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 |
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).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 (the animation below — watch how 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.
This section has a step-by-step animation in the interactive lesson.