Finding one thing in a pile of things is one of the most common jobs a program does: is this username taken, where is this word in the dictionary, which row has this order number. There are two classic ways to do it. Linear search checks items one by one. Binary search keeps cutting the pile in half. On a list of a billion items, the first can need a billion checks; the second never needs more than 30. This page shows you why, with a game, a race and a few lines of Python.

Start with a game

You've probably played this as a kid. I'm thinking of a whole number from 1 to 100. You guess, and I only ever say higher, lower or got it. How many guesses do you need?

Play a round below. The green band shows the numbers that are still possible after each answer.

If you guessed 1, then 2, then 3 and so on, you could need up to 100 guesses. That's linear search: walk the line, one item at a time. If instead you always guessed the middle of what's left, you never needed more than 7. That's binary search. "Binary" here just means "in two": every guess splits the remaining numbers into two halves and throws one half away.

The trick only works because the numbers 1 to 100 are in order. When I say "higher" after you guess 50, you know for sure that 1 to 50 are all wrong, because they're all smaller than 51. One answer rules out fifty numbers at once.

Searching a list

In a program, the "pile" is usually a list, also called an array: a row of values, each sitting at a numbered position called its index. Python counts indexes from 0, so in [4, 9, 15] the value 4 is at index 0 and 15 is at index 2. Searching means: given a target value, tell me its index, or tell me it isn't there.

Linear search works on any list. Start at index 0, compare, move to index 1, compare, and stop when you find the target or run out of list.

Binary search needs the list to be sorted (smallest to largest). It keeps two markers, low and high, around the part of the list where the target could still be. Each step looks at the middle item between them:

1. If the middle item is the target, done.
2. If the middle item is smaller than the target, the target can only be to the right, so move low just past the middle.
3. If it's bigger, the target can only be to the left, so move high just before the middle.
4. If low passes high, there's nothing left to check: the target isn't in the list.

Here both methods race on the same sorted list of 40 numbers. Each "step" is one comparison: looking at one item and checking it against the target. Pick a target (or one that's missing) and press Step.

Try a few targets near the end of the list, and try a missing one. Linear search pays the most when the target is near the end or absent: it has to look at every single item before it can say "not here". Binary search's green-bordered window shrinks by half each step, and it never needs more than 6 steps for these 40 numbers.

To be fair to linear search: if the target happens to be the very first item, it wins in one step. Binary search would start in the middle. Programmers usually care about the worst case, the most steps a method could ever need, because that's what decides whether your program stays fast when the data gets big.

Counting the steps: what log₂ means

For linear search, the worst case is easy: a list of n items can take n steps. Double the list, double the work.

For binary search, ask a different question: how many times can you halve n before only one item is left? Start with 100: 50, 25, 12, 6, 3, 1. That's 6 halvings, plus one last look at the single remaining item, so 7 steps. Mathematicians have a name for "how many times do I halve to get down to 1": the base-2 logarithm, written log₂. It's the opposite of doubling. Because 2¹⁰ = 1,024, log₂ of 1,024 is 10.

The exact worst case for binary search on n items is log₂(n), rounded down, plus 1. You don't need to memorise that. The feeling to remember is this: every time the list doubles, binary search needs just one more step.

Drag the slider to feel how differently they grow. The bars use the same scale, so binary's bar quickly becomes a sliver.

Programmers describe this growth with Big O notation: linear search is O(n) ("grows in step with the size") and binary search is O(log n) ("grows with the number of halvings"). You'll see those labels in documentation and job interviews; now you know what they're pointing at.

Both in Python

Here are both methods as Python functions. Each one returns two things: the index where it found the target (or -1 if it isn't there, a common convention), and how many steps it took, so we can compare.

def linear_search(items, target):
    steps = 0
    for i in range(len(items)):
        steps += 1
        if items[i] == target:
            return i, steps
    return -1, steps


def binary_search(items, target):
    low = 0
    high = len(items) - 1
    steps = 0
    while low <= high:
        steps += 1
        mid = (low + high) // 2
        if items[mid] == target:
            return mid, steps
        elif items[mid] < target:
            low = mid + 1    # target is in the right half
        else:
            high = mid - 1   # target is in the left half
    return -1, steps


numbers = list(range(0, 2000, 2))   # 0, 2, 4, ... 1998  (1000 items)

print(linear_search(numbers, 1500))
print(binary_search(numbers, 1500))
print(linear_search(numbers, 7))
print(binary_search(numbers, 7))

Running it prints:

(750, 751)
(750, 9)
(-1, 1000)
(-1, 10)

Both agree that 1500 sits at index 750. Linear search needed 751 looks to get there; binary search needed 9. For 7, which isn't in the list (it's odd, and the list only has even numbers), linear search checked all 1,000 items while binary search gave up confidently after 10, exactly the worst case from the table.

A few details worth a second look:

• // is floor division: divide and throw away the remainder. (0 + 999) // 2 is 499, a valid whole-number index. A plain / would give 499.5, and Python refuses to use a decimal as a list index.
• low = mid + 1 (not low = mid) matters: we already checked mid, so skip it. Forget the + 1 and the loop can get stuck forever on the same two items. This is the classic binary-search bug.
• while low <= high uses <=, not <, so that a window of exactly one item still gets checked.

So why not always use binary search?

Because of that one requirement: the list must be sorted. Binary search on an unsorted list doesn't crash. It just quietly gives wrong answers, because "smaller than the middle, so it must be on the left" is no longer true. (The quiz below has an example.)

Sorting takes work too, more work than a single linear search. So the rough rule is:

• Searching once in unsorted data, or in a small list (a few dozen items)? Linear search is simple and perfectly fine.
• Searching many times in big data? Sort it once (or keep it sorted as you add items), then binary search every time. The sorting cost is paid once; the savings come on every search.

This idea of keeping data in order so you can halve your way to an answer shows up everywhere: database indexes, dictionaries, even git bisect, a tool that finds which change introduced a bug by repeatedly testing the commit halfway between "worked" and "broken".

Check yourself

The short version

• Linear search checks items one by one. Works on any list. Worst case: n steps for n items.
• Binary search checks the middle and throws away half each time. Only works on sorted data.
• Its worst case is about log₂(n) steps: doubling the list adds one step. A billion items need at most 30.
• In Python, the midpoint is (low + high) // 2, and moving low or high past mid (the + 1 / - 1) keeps the loop from getting stuck.
• Small list, or searching once? Linear is fine. Big list, searched often? Keep it sorted and use binary search (Python's bisect module).

Next time you play "guess my number", you'll know the winning strategy has a name, and that it's the same one your computer uses millions of times a day.