Binary Search

Imagine I'm thinking of a number between 1 and 100, and you have to guess it — but after every guess I'll tell you only "higher" or "lower". You could start at 1 and crawl upwards, but that might take a hundred guesses. The clever player always guesses the middle: "50?" If I say "higher", every number from 1 to 50 is instantly ruled out — half the possibilities gone in one guess. Then you guess the middle of what's left, and the middle of that, until only my number remains.

That is binary search: a way of finding something in a sorted list by repeatedly looking at the middle item and throwing away the half that can't possibly contain what you're after. "Binary" means "two", and it's the perfect name — each step splits the list in two and keeps just one half.

You already do this without thinking. To find "otter" in a dictionary you don't read from "aardvark" — you flop it open near the middle, land on "lemur", and instantly ignore the entire first half. The words being in order is what makes that leap safe, and it's exactly the secret behind binary search.

The idea, step by step

We track the slice of the list still worth searching with two markers: low (the first index that might hold the target) and high (the last one). The item bang in the middle is at index mid, which is just the average of the two, rounded down:

\text{mid} = \left\lfloor \dfrac{\text{low} + \text{high}}{2} \right\rfloor

Each round, we compare the middle item with the target and do one of three things:

We repeat while low is still at or before high. If the two markers ever cross over — low greater than high — the slice is empty, which means the target simply isn't in the list.

Watch the window shrink

Here is a sorted list of 11 numbers, and we're hunting for 23. Step through and watch the low…high window collapse: every step at least halves the shaded region still in play.

Notice we found 23 after checking only three items — 17, then 42, then 23 — never touching the other eight. Every comparison earned its keep by deleting a whole half of what was left.

Binary search in code

Here is the whole algorithm in TypeScript. It console.logs the window and the item it checks on every round, so you can see the halving happen. Press Run:

function binarySearch(list: number[], target: number): number { let low: number = 0; // first index still in play let high: number = list.length - 1; // last index still in play while (low <= high) { // keep going while the window isn't empty const mid: number = Math.floor((low + high) / 2); console.log(`Searching [${low}..${high}], checking index ${mid} = ${list[mid]}`); if (list[mid] === target) { return mid; // found it — hand back the index } else if (list[mid] < target) { low = mid + 1; // target is bigger → discard the LEFT half } else { high = mid - 1; // target is smaller → discard the RIGHT half } } return -1; // low passed high → not in the list } const numbers: number[] = [3, 8, 15, 17, 23, 31, 42, 56, 60, 78, 91]; console.log("Found 23 at index:", binarySearch(numbers, 23)); console.log("Found 91 at index:", binarySearch(numbers, 91)); console.log("Looking for 50:", binarySearch(numbers, 50)); // not present → -1

Read the log for 23: the window shrinks from [0..10] to [0..4] to [3..4], closing in with each line. Searching for 50 never finds it, so low eventually overtakes high, the loop ends, and we return -1.

Why it's so fast: about \log_2 n steps

Its rival, linear search, checks items one by one from the start. In the worst case (the target is last, or missing) it must look at every item — n checks for a list of n. Binary search instead halves the list each step, so the number of checks is roughly how many times you can halve n before nothing is left — that's the logarithm base two, \log_2 n:

The gap is staggering as the list grows. For a list of 1000 items, linear search may need 1000 checks; binary search needs only about 10, because 2^{10} = 1024. Double the list to 2000 and linear search doubles its work — but binary search needs just one extra check. A phone book of a million names? Around 20 checks. That is the magic of logarithmic growth.

// How many halvings before a list of n items is down to nothing? function stepsNeeded(n: number): number { let count: number = 0; while (n > 0) { n = Math.floor(n / 2); count++; } return count; } for (const size of [10, 100, 1000, 1_000_000]) { console.log(`${size} items → at most ${stepsNeeded(size)} checks`); }

Because binary search demands a sorted list, and sorting isn't free — it costs more work than a single linear scan. So if you're going to search a list just once, plain linear search is often the sensible choice. Binary search wins big when the list is already sorted, or when you'll search it many times: you pay to sort once, then every lookup afterwards is lightning-fast. Databases lean on exactly this trade — they keep data in sorted "indexes" so that countless later searches each cost only a handful of steps.

Binary search only works on a sorted list. The whole method rests on one promise: if the target is bigger than the middle item, it must be to the right; if smaller, to the left. On an unsorted list that promise is broken, so throwing away a half is a reckless gamble — the target might be sitting in the half you just discarded. It won't crash; it will calmly return the wrong answer, usually -1 ("not found") for an item that is really there.

const jumbled = [42, 8, 91, 15, 3]; // NOT sorted! binarySearch(jumbled, 91); // checks middle (91)? no — logic misleads it → wrong result

The fix is simple: sort first, then binary-search. If you can't sort (or the data keeps changing), reach for linear search instead — it never assumes any order, so it always gives the right answer, just more slowly.