AP® Computer Science Principles · Big Idea 3 · Topic 3.11
Counting Binary Search Steps
Binary search cuts the list in half with every comparison, so the number of steps needed grows with log base 2 of the list size, not with the size itself. Doubling the list only costs one extra step.
Binary search works on a sorted list by checking the middle item, then throwing away half the list, every time. If the middle item is too big, the answer must be in the left half; too small, and it must be in the right half. Each comparison removes half of what is left, so the question becomes: how many times can you cut a number in half before you land on 1? For a list of 2k items, the answer is exactly k comparisons in the worst case. That is why a list of a million items, roughly 220, needs only about 20 comparisons to find an item or prove it is missing.
This is also why doubling the list barely costs anything. Going from 1000 items to 2000 items does not double the work; it adds one more halving step, because 2000 is still close to the same power of 2 as 1000 give or take a step. Compare that to linear search, which checks items one at a time from the front: doubling the list doubles the worst case number of comparisons. Racing both on a sorted list of 64 values, linear search can take up to 64 comparisons, but binary search needs at most 6, since 26 = 64.
That speed depends entirely on the list already being sorted. Sorting an unsorted list first has its own real cost, often far higher than a single linear search would ever cost. So binary search only pays off when the list is sorted already or will be searched many times, spreading that sorting cost across many fast searches.
Key terms
- Binary search
- A search algorithm that repeatedly checks the middle of a sorted list and discards the half that cannot contain the target.
- Worst case
- The largest number of steps an algorithm could ever need, used to describe its slowest possible run.
- Logarithmic growth
- A pattern where the number of steps grows by a fixed amount each time the input size doubles, rather than growing proportionally.
- Linear search
- A search algorithm that checks each item one by one from the start until it finds the target or reaches the end.
Watch it explained
- How it worksHow does repeated halving turn a list of a million into about twenty comparisons?
- Worked exampleFind the maximum number of steps a binary search needs on a sorted list of 1000 items.
- Worked exampleShow me linear search and binary search racing each other on the same sorted list of 64 values.
- Ties togetherHow does the cost of sorting a list first change whether binary search is worth using?
Check yourself
End of topic.