cf.completefrontend
SEARCHING & BINARY SEARCH · FOUNDATION

Binary search

Find a value in a sorted list by checking the middle and throwing away the half that can't hold it.

Time O(log n)Space O(1)25 practice problemsStep-through picture

The idea

Binary search finds a value in a sorted list. It looks at the middle item first. If the middle item is too small, the value can only be in the right half, so it forgets the left half. If the middle item is too big, it forgets the right half. Then it repeats with the half that is left.

Each check throws away half of the items that are still possible. A list of 1,000 items needs at most 10 checks, and a list of a million items needs at most 20. A simple loop that checks every item could need a million checks.

The one rule: the list must be sorted. Binary search only works because a sorted list tells you which side the value must be on.

An everyday example

Guessing a number from 1 to 100

A friend thinks of a number from 1 to 100 and answers each guess with "higher" or "lower". You don't guess 1, then 2, then 3. You guess 50. If they say "higher", every number from 1 to 50 is gone in one guess, so you guess 75 next. You always guess the middle of the numbers that are still possible, and you find any number in at most 7 guesses.

How the example maps to the code
In the exampleIn the code
The numbers that are still possibleThe range from low to high
Guessing the middle numbermid = Math.floor((low + high) / 2)
"Higher": forget the numbers below your guesslow = mid + 1
"Lower": forget the numbers above your guesshigh = mid - 1
"That's it!"return mid

From the slow way to binary search

  1. Start with the obvious way: check every item from the left until you find the target. That's linear search. On a list of 1,000,000 items it can take 1,000,000 checks, and it ignores the most useful fact we have: the list is sorted.
  2. Sorted means every item is at least as big as the one before it. So one check tells you more than "is this the target?". If items[i] is smaller than the target, then every item to the left of i is smaller too, and none of them can be the target. One comparison rules out a whole side.
  3. Which item should you check first, to rule out the most? If you check near the left end and lose, you only rule out a few items. If you check the middle, then whichever way the comparison goes, you rule out half of the items. Checking the middle is the choice that wins the most in the worst case.
  4. Now keep the part that's left as a range with two numbers: low is its first index and high is its last. Check the middle of that range, then move low or high past the middle to drop the half that can't hold the target. Repeat until you find the target or the range is empty. That loop is binary search.

How it works

  1. Start with low at the first index and high at the last index. Every index from low to high might hold the target.
  2. While low is not past high, pick the middle index: mid = Math.floor((low + high) / 2).
  3. If the item at mid is the target, you're done: return mid.
  4. If the item at mid is smaller than the target, the target can only be to the right, so move low to mid + 1.
  5. Otherwise the item at mid is bigger, so the target can only be to the left: move high to mid - 1.
  6. If low passes high, no index is left to check, so the target isn't in the list: return -1.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function binarySearch(items, target) {
  2. let low = 0;
  3. let high = items.length - 1;
  4. while (low <= high) {
  5. const mid = Math.floor((low + high) / 2);
  6. if (items[mid] === target) return mid;
  7. if (items[mid] < target) {
  8. low = mid + 1;
  9. } else {
  10. high = mid - 1;
  11. }
  12. }
  13. return -1;
  14. }

How fast it is

TimeO(log n)
Extra memoryO(1)

Every loop halves the range that is left, so it runs about log₂ n times. It only keeps three numbers (low, high, mid), whatever the list's size.

  • Best caseO(1)

    The target is the very first middle item, so the first check finds it.

  • Average caseO(log n)

    A target at a random position is usually found only after the range has shrunk to a few items, close to the worst case.

  • Worst caseO(log n)

    The target isn't in the list, or sits where it's checked last. The range halves each time until it's empty: about log₂ n checks, 20 for a million items.

Common mistakes

  • Running it on a list that isn't sorted. It returns wrong answers without any error, so sort first or use a plain loop.
  • Writing while (low < high) with high = mid - 1. The loop stops while one item is still unchecked.
  • Writing low = mid instead of low = mid + 1. When low and high are next to each other, mid equals low forever and the loop never ends.
  • Comparing strings of digits, like "10" < "9", which is true because strings compare letter by letter. Convert to numbers first.

When to use it

Look for these clues in a problem:

  • The input is sorted, or you can sort it without losing what the question asks for.
  • The question asks you to find a value, its position, or the first or last position where something becomes true.
  • The input is huge (say a million items) and a simple loop over it would be too slow.
  • The problem says the answer must run in O(log n) time.

Check yourself

Answer each one in your head first, then open it.

Why must the list be sorted?

Because one comparison only rules out a whole side when the list is sorted. In an unsorted list, a small middle item says nothing about the items to its left.

What goes wrong with while (low < high) and high = mid - 1?

The loop stops while one item, at low === high, is still unchecked, so a target sitting there is missed.

About how many checks does it need for 1,000 items?

About 10, because 2 to the 10th power is 1,024. Each check halves the range: 1,000, 500, 250, and so on down to 1.

Why does low = mid (without + 1) risk an endless loop?

When low and high are next to each other, mid equals low, so low = mid changes nothing and the loop repeats forever.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 25 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one promise, checked at the top of every loop: if the target is anywhere in the list, it is somewhere from low to high. At the start, the range is the whole list, so the promise is true.

Each step keeps the promise. When items[mid] < target, every item from index 0 to mid is at most items[mid], because the list is sorted, so none of them can equal the target. Moving low to mid + 1 throws away only items that can't be the answer. The same reasoning covers moving high to mid - 1 when items[mid] is too big.

The loop always ends, because every step makes the range at least one item shorter: mid sits inside the range, and the new range leaves mid out. So either it finds the target, or the range becomes empty. An empty range plus the promise means the target was never in the list, so returning -1 is correct.

Going deeper

3 more ideas

The rule the loop keeps

At the start of every loop, if the target is in the list at all, it is somewhere from low to high. The loop only ever throws away items that can't be the target, so this stays true. When the range is empty (low > high), the target was never there.

Why it's called O(log n)

Each check halves the range. Starting from n items, after one check about n / 2 are left, then n / 4, then n / 8. The number of halvings until one item is left is the base-2 logarithm of n, written log n. That's why 1,000,000 items need only about 20 checks.

Why <= in the loop condition

When low equals high, one item is still possible, and it must be checked. With while (low < high) the loop would stop one item early and miss a target sitting in that last spot.

Work it by hand

Every step in a table, with why

Look for 20 in a sorted list of 9 numbers. It isn't there, so the trace shows every step until the range is empty.

items = [3, 11, 14, 19, 27, 31, 40, 46, 58], target = 20

Steplowhighmiditems[mid]What happensWhy
10842727 > 20, so high = 3The whole list is possible. The middle item, 27, is too big, so the target can only be to its left.
20311111 < 20, so low = 2Four items are left. 11 is too small, so drop it and everything before it.
32321414 < 20, so low = 3mid rounds down to 2. 14 is too small, so only index 3 is left.
43331919 < 20, so low = 4low equals high: one item is left, and the loop still checks it. This is why the condition is low <= high.
543--low > high: stopThe range is empty, so no item can be the target.

It returns -1 after 4 checks. A linear search would have checked 5 items before reaching 27 and knowing it had gone too far.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Binary searchO(log n)O(1)The list is sorted and you'll search it more than once, or it's too big to scan.
Linear searchO(n)O(1)The list isn't sorted, is tiny, or you'll only search it once: sorting first would cost more than scanning.
Hash set lookupO(1)O(n)You only ask "is it there?", never "where would it go?" or "what's the nearest value?", and can spend memory on a set.

Extra memory: O(1): three numbers, low, high, and mid, whatever the list's size. A recursive version uses O(log n) space for its call stack instead.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Binary search and the other approaches, on a scale where each line up is 10 times more steps.
  • Binary search O(log n)
  • Linear search O(n)
  • Hash set lookup O(1)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Binary search31020
Linear search101,0001 million
Hash set lookup111

Inputs that need care

5 tricky inputs
An empty list: items = []
high starts at -1, so low <= high is false at once and it returns -1. No special check is needed.
One item: items = [7]
low and high are both 0. The loop runs once, checks items[0], and either returns 0 or ends with an empty range.
The target is smaller than everything, or bigger than everything
The range shrinks toward one end until it's empty, and the result is -1. If you need to know where the target would go, use lower bound instead.
Duplicates: items = [2, 4, 4, 4, 9], target 4
It returns the index of whichever 4 a middle check lands on, here 2. If you need the first or last copy, use lower bound or upper bound.
Very large indexes
In JavaScript, low + high can't overflow for any array that fits in memory. In languages with 32-bit integers, write low + Math.floor((high - low) / 2) to stay safe.

Variations and follow-ups

Twists interviewers add

Lower bound and upper bound

Instead of stopping at any match, keep going to find the first index whose item is >= target (lower bound) or > target (upper bound). They answer "where would this go?" and "how many copies are there?" (upper bound minus lower bound).

Binary search on the answer

Sometimes there's no list at all, just a yes-or-no question that flips once as a number grows, like "can we ship every package within d days?". Binary search the number d itself: check the middle value, and keep the half where the answer flips.

Search a rotated sorted list

A sorted list cut in two and swapped, like [40, 46, 58, 3, 11], still has one sorted half at every middle check. Find which half is sorted, check whether the target falls inside it, and keep that half or the other one.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from the words "sorted", "find the first or last", "minimum value that works", or a size limit like 10^5 with a fast time limit: O(log n) per question is the hint.
  • Say the promise out loud before coding: "if the target is anywhere, it's between low and high". Then each line of the loop is easy to defend, and off-by-one bugs are easy to spot.
  • Test three tiny inputs by hand before saying you're done: an empty list, one item, and a target bigger than every item. Most bugs show up in one of them.
  • Expect the follow-up "what if there are duplicates and you need the first one?". The answer is lower bound: when you find a match, keep searching left with high = mid - 1 and remember mid.

Where frontend code uses it

The same idea in real UI code
  • Virtualized lists (long feeds and tables that only render the rows on screen) binary search the rows' running heights to find which row sits at the current scroll position.
  • Source maps binary search sorted position mappings to turn a minified line and column back into your original code.
  • Animation timelines and charts binary search sorted timestamps to find the keyframe or data point under the cursor.
  • git bisect, which you may use to find the commit that broke a page, is binary search over your commit history.

Related algorithms