AlgoScope

Binary Search

algorithmbeginnerTime O(log n)Space O(1)

Look at the middle. Throw away the half that cannot contain the target. Repeat.

active 0-9205182123164235386567728919lowhigh

Search for 56. The whole sorted array is in play.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 2, with their answers.

  1. Middle value is 16 and the target is 56. What happens next?

    • Search left
    • Search right
    • Found it

    Answer: Search right. 16 is smaller than 56, so everything at or before the middle is discarded.

  2. Middle value is 56 and the target is 56. What happens next?

    • Search left
    • Search right
    • Found it

    Answer: Found it. 56 equals 56, so the search is over.

How it runs, step by step

  1. Search for 56. The whole sorted array is in play.

    Searching for 56 in a sorted array of 10 values, from 2 to 91. Low pointer at index 0, high pointer at index 9.

  2. The middle of indices 0 to 9 is index 4, which holds 16.

    Middle of the range from index 0 to 9 is index 4, value 16.

  3. 16 is smaller than 56, so 56 can only be to the right. Discard 5 values.

    Comparing target 56 with middle value 16 at index 4. 16 is smaller, so the target must be to the right. Discarding indices 0 to 4. Now searching indices 5 to 9.

  4. The middle of indices 5 to 9 is index 7, which holds 56.

    Middle of the range from index 5 to 9 is index 7, value 56.

  5. 56 equals 56. Found it at index 7.

    Comparing target 56 with middle value 56 at index 7. They are equal. Found at index 7.

  6. Found 56 at index 7 after 2 comparisons.

    Result: 56 found at index 7 after 2 comparisons.

Write it yourself

Define binarySearch(values, target) and return the index of the target, or -1 when it is not there. It runs in your browser against this lesson's own 8 examples.

// The array is sorted. Look at the middle and throw away the half that cannot hold the target.function binarySearch(values, target) {    return -1;}
Ln 1, Col 16 linesTab indents; Escape then Tab leaves the editor. Ctrl-Enter runs, Cmd-Enter on a Mac.

Remember

  • Only works on sorted data.
  • Every comparison halves what is left, so 1,000 values need about 10 looks.
  • When low passes high, the target is not there.

Topics covered

Related

Where this is used

DatabasesDatabase indexes

A B-tree index is binary search generalised to disk: each node holds many keys so one read narrows the range by a large factor instead of by half. The reason an indexed lookup is instant and a full scan is not is exactly this halving.

Developer toolsgit bisect

Finding which commit introduced a bug is binary search over history. Each test you run halves the range of suspect commits, which is why bisecting a thousand commits takes about ten builds rather than a thousand.

TextAutocomplete and spell check

A sorted word list plus binary search finds the range of words sharing a prefix in a few comparisons, which is how a suggestion list appears while you are still typing.

OperationsFinding a tipping point

Binary search works on any yes-or-no question whose answer flips once: the smallest server size that handles the load, the highest quality that fits a bandwidth budget. You are searching the answer space, not an array.

Why it works this way

Why the middle, and not a third of the way in?

Whichever element you compare against, the worst case is the larger of the two remaining sides. The middle makes those two sides equal, so it minimises the worst case. Probing a third of the way in is faster when you get lucky and slower when you do not.

Why low + (high - low) / 2 instead of (low + high) / 2

They are equal mathematically, but low + high can overflow a 32-bit integer for large arrays. This bug sat in the JDK's own binary search for nine years. The form used here can never overflow.

The loop must shrink the range every time

low = mid + 1 and high = mid - 1 both exclude the element just compared. Writing low = mid instead is the classic infinite loop: when low and high are adjacent, mid equals low and nothing changes.

With duplicates it finds a match, not the first one

The version here stops at whichever equal element the midpoint lands on. To find the first or last occurrence you keep searching after a match instead of returning: that is the lower bound and upper bound variant.

Read more

Next up