Binary Search
Binary search is the reward you get for keeping data sorted: instead of checking values one by one, check the middle. Too small? The target can only be in the right half. Too big? Left half. Every single check cuts the problem in half - so a million values need at most 20 checks, and a billion need 30. It is the biggest speed jump in this whole collection, and also the algorithm with the most famous off-by-one bugs.
Watch it search
Press play - or drag the timeline and step through it yourself.The array is sorted - that is the requirement. Find 31 among 18 values by halving the range each step.
Complexity
The number guessing game
"I am thinking of a number between 1 and 100." Nobody guesses 1, then 2, then 3. You guess 50. "Too low." Now you know it is 51-100, so you guess 75. "Too high." It is 51-74... Each answer kills half the possibilities, and you corner any number in at most 7 guesses. Binary search plays exactly this game against a sorted array - the sorted order is what makes "too low / too high" meaningful.
How it works, step by step
Keep two markers: lo (start of the possible range) and hi (end of it). At first, that is the whole array.
Look at the middle value of the range.
If it is the target - done.
If it is smaller than the target, the target can only be to its right: move lo to mid + 1.
If it is bigger, move hi to mid − 1.
Repeat. The range halves each time; when it becomes empty, the target is not there. That is log₂(n) checks at most.
The code, in JavaScript
The classic loop. Every line matters - most binary search bugs come from changing one of them carelessly.
function binarySearch(arr, target) {
let lo = 0;
let hi = arr.length - 1;
while (lo <= hi) { // <= : a 1-value range still counts
const mid = (lo + hi) >> 1; // middle, rounded down
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1; // target is right of mid
else hi = mid - 1; // target is left of mid
}
return -1; // range is empty - not found
}
binarySearch([2, 5, 8, 12, 16, 23, 38, 56], 23); // → 5
binarySearch([2, 5, 8, 12, 16, 23, 38, 56], 20); // → -1Dry run: searching a sorted array of 8 values
The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.
| Step | Step | Array | What happened |
|---|---|---|---|
| 1 | 1 | [2, 5, 8, 12, 16, 23, 38, 56] | Middle is 12 < 23 - the target must be to the right. Throw away the left half. |
| 2 | 2 | [2, 5, 8, 12, 16, 23, 38, 56] | Middle of [5..8] is position 6: 23 - that is the target! |
Good choice when…
- The data is sorted (or you can sort it once) and you look things up repeatedly - each lookup drops from O(n) to O(log n).
- You need first/last occurrence, insertion points, or "how many values are below x" - the lowerBound variant answers all of these.
- The answer to a problem is a number where a yes/no test flips once ("smallest capacity that works") - binary search the answer space.
- The dataset is too big for a hash map but sits sorted on disk - databases live on this exact idea (B-trees are its generalization).
Bad choice when…
- The data is unsorted and searched once - sorting first costs O(n log n), more than one O(n) scan.
- The data changes constantly - keeping an array sorted costs O(n) per insert; a tree or skip list fits better.
- You look up by exact key many times and order never matters - a Map is O(1) and has no edge cases.
Common mistakes
- `lo <= hi` versus `lo < hi` is not a style choice - it depends on whether `hi` starts at `length - 1` or `length`. Mixing the two conventions produces a search that misses the last element, or loops forever.
- In most languages `(lo + hi) / 2` can overflow with big indexes; the safe form is `lo + (hi - lo) / 2`. JavaScript's numbers survive it, but `(lo + hi) >> 1` breaks past 2³¹ - know your sizes.
- Forgetting the +1/−1 (`lo = mid` instead of `lo = mid + 1`) creates the classic infinite loop on a 2-element range. If your binary search hangs, look there first.
- The precondition is silent: run it on an unsorted array and it returns confident nonsense, no error. The famous 2006 Java bug shows even standard libraries got binary search wrong for years.
Binary Search vs. its closest relatives
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Binary Searchthis page | O(1) | O(log n) | O(log n) | O(1) | - |
| Linear Search | O(1) | O(n) | O(n) | O(1) | - |
| Two Pointers | O(n) | O(n) | O(n) | O(1) | - |
| Binary Search Tree | O(log n) | O(log n) | O(n) | O(n) | - |