Binary Search Steps

In one sentence: Binary search finds an item in a sorted list by checking the middle and throwing away half, and this formula counts how many checks that takes at most.

$\text{steps} = \lceil \log_2 (n + 1) \rceil$

Read it out loud: “The number of steps equals the ceiling of the base-2 logarithm of n plus 1. The ceiling means round up to the next whole number.”

What each symbol means

Symbol	Meaning
$\text{steps}$	The worst-case number of comparisons: how many checks you might need before you know whether the item is in the list.
$n$	How many items are in the sorted list.
$\log_2 x$	The base-2 logarithm: how many times you must halve $x$ to get down to 1. For powers of 2 it is exact, so $\log_2 8 = 3$ because $8 \to 4 \to 2 \to 1$ takes 3 halvings.
$\lceil x \rceil$	The ceiling of $x$ : round $x$ up to the next whole number. For example $\lceil 19.93 \rceil = 20$ .

What the formula is doing

Suppose you look for a name in a phone book with 1,000,000 names in alphabetical order. You do not start at the first page. You open the book near the middle, see where your name falls, and ignore the half that cannot contain it. Then you repeat the same move on the half that is left.

Each check cuts the remaining pages in half. Start with $n$ names. After one check about half remain, after two checks about a quarter remain, and so on. The search is over when only one name is left to check, or sooner if you find the name.

The number of checks is the number of halvings until one item is left, and that count is a logarithm: $\log_2 n$ counts the halvings. The formula uses $n + 1$ and rounds up with the ceiling. That covers lists that do not split evenly, and it gives the worst-case count for every list length.

The shape matters because every extra step lets you handle a list twice as long. A list twice as long needs only one extra check, which is why binary search stays fast even when the list is huge.

An everyday picture

A phone book is the perfect picture. Open it in the middle, decide which half your name is in, and ignore the other half. You never page through the whole book one name at a time. With a million names you need only about 20 looks.

Worked example: Finding one name among 1000000 sorted items

A sorted list has $n = 1000000$ items. We want the worst-case number of comparisons for binary search, and we compare it with a plain linear scan that checks one item at a time.

Add 1: $n + 1 = 1000001$ .
Take the base-2 logarithm: $\log_2 1000001 \approx 19.93$ . So you need about 20 halvings to get down to one item.
Round up with the ceiling: $\lceil 19.93 \rceil = 20$ steps.
A linear scan may check all $1000000$ items in the worst case. The ratio is $\frac{1000000}{20} = 50000$ , so binary search does about 50,000 times fewer checks here.

Answer: In the worst case, binary search needs 20 comparisons to find an item in a sorted list of one million items. A linear scan may need up to 1,000,000. The gap grows fast as the list grows.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Running binary search on a list that is not sorted. The halving only works when you know which side of the middle the item is on, and that needs sorted data.
Reading the formula as the number of checks you always need. It gives the worst case. Sometimes the item turns up on the first check.
Leaving out the ceiling and reporting 19.93 steps. Steps are whole checks, so round up to 20.
Using the natural logarithm when the halving is in base 2. Use $\log_2$ , or convert from another base with a division.

Where you will meet it

Searching sorted arrays in programming libraries, for example Python’s bisect module, which uses binary search.
Looking up values in sorted data, such as a sorted list of names or timestamps.
Debugging with git bisect, which halves the list of commits to find the one that introduced a bug.
The classic guessing game: if you guess a number from 1 to 100 and get higher-or-lower hints, binary search needs at most 7 guesses.

Questions people ask

Why does the formula use $n + 1$ and not $n$?

The $+1$ makes the formula give the worst-case count for every list length, including lists that do not split evenly. A list of 1 item gives $\lceil \log_2 2 \rceil = 1$ check, and a list of 3 items gives $\lceil \log_2 4 \rceil = 2$ checks.

Is binary search always faster than a linear scan?

On a sorted list it is never slower in the worst case, and for long lists it is far faster. For 10 items the gap is small in absolute terms, because a linear scan may need 10 checks and binary search at most 4. The gap grows quickly as the list grows.

Does binary search need the list to be sorted first?

Yes. The halving depends on knowing which side of the middle the item is on, and only sorted data guarantees that. Sorting costs time up front, so it pays off when you search the same list many times.

Binary Number Value: Binary uses only the digits 0 and 1, and this formula turns a row of those digits into the ordinary number they stand for.
Little's Law: Little’s law says the number of things inside a system equals how fast they arrive, multiplied by how long each one stays.
Amdahl's Law: Amdahl’s law tells you how much faster a whole program gets when you speed up only part of its work, and why the part you leave alone caps the gain.