Binary search, explained

Binary search is like guessing a number between 1 and 100 when someone tells you "higher" or "lower" after each guess. If you always guess the middle, you cut the possibilities in half every time.

It only works on a sorted list, because the order is what tells you which half to discard.

How it works

• Look at the middle item of the current range.
• If it equals the target, you are done.
• If the target is smaller, keep only the left half. If it is bigger, keep only the right half.
• Repeat until you find the target or the range is empty.

A small example

Search for 23 in this sorted list:

2 5 8 12 16 23 38 56 72 91

Binary search checks 16 (too small), then 56 (too big), then 23 (found), so it takes:

3 checks

Linear search needed 6 checks for the same target.

What to know about its cost

• Best case O(1).
• Average and worst case O(log n): doubling the list adds only one more check.
• Needs a sorted list and uses O(1) extra space.

Where it works well

• Extremely fast on large sorted lists.
• A list of a million items needs only about 20 checks.

Where it struggles

• The list must be sorted first, which costs time if it is not.
• Needs fast access to the middle item, so it suits arrays better than linked lists.

Try it yourself

Open the Searching experiment, enter the list from this post, set the target to 23, choose Binary Search and step through it. Then compare it with the other algorithms and look at how many positions each one checks.

Open the Searching experiment