Sonith ManakkatFinding things is the most common job a computer does. This part compares two classic methods, linear search and binary search, as animations you can watch, then adds an Expert view with the exact invariants, costs and traps. If you prefer no motion, each animation includes its steps as text.
The phone-book picture
Imagine looking for one name in a printed phone book. You could start at page one and read every name until you find it. Or, because the names are in alphabetical order, you could open the book in the middle and decide which half holds your name.
Linear search
- Check every name from the start
- Works even if the names are jumbled
Binary search
- Open in the middle, keep the right half
- Only works if the names are in order
Expert viewProblem statement
Given a collection and a target key, return the position of an item with that key, or report that none exists. Two things decide the choice of method: whether the data is ordered by the key, and whether it supports random access (jumping straight to position i, as arrays do, but linked lists do not). Binary search needs both.
Linear search: look at everything
Show the 6 steps as text
- Goal: find 41. Start at the first card.
- Look at 14: not 41, move on.
- Look at 3: not 41, move on.
- Look at 22: not 41, move on.
- Look at 9: not 41, move on.
- Look at 41: found it after 5 looks.
function linearSearch(list, target):
for i from 0 to length(list) - 1:
if list[i] == target:
return i
return NOT_FOUNDExpert viewCost of linear search
Best case: 1 comparison (the target is first), O(1). Worst case: n comparisons (last or absent), O(n). Average case for a target that is present and equally likely anywhere: about n / 2 comparisons, still O(n). Extra space is O(1). It needs no ordering, works on linked lists and streams, and can use any equality test, which makes it the most general method.
Binary search: halve a sorted list
Show the 5 steps as text
- Goal: find 41 in a sorted row. Always look at the middle.
- Middle is 28, too small: throw away the left half.
- Middle is 47, too big: throw away the right half.
- Middle is 35, too small: throw away the left half.
- Middle is 41: found it after 4 looks.
function binarySearch(list, target): // list is sorted
low = 0
high = length(list) - 1
while low <= high:
mid = low + (high - low) / 2 // whole-number division
if list[mid] == target:
return mid
else if list[mid] < target:
low = mid + 1
else:
high = mid - 1
return NOT_FOUNDExpert viewThe invariant: low, high and mid
Correctness rests on one statement that stays true at the start of every loop pass: if the target is in the list, it lies at an index between low and high inclusive. Each pass looks at mid, and then moves low above it or high below it, so the range shrinks while the statement stays true. When low passes high, the range is empty, so the target is absent. Stating the invariant first is the reliable way to write the loop.
Expert viewTraps: off-by-one and midpoint overflow
Off-by-one mistakes are the classic bug. Decide whether high is inclusive or exclusive, then keep the loop condition, the updates (mid + 1, mid - 1) and the initial value consistent with that choice. Mixing conventions can cause an infinite loop or a missed element.
With fixed-size integers, computing the midpoint as (low + high) / 2 can overflow when low and high are both large, giving a wrong index. Writing low + (high - low) / 2 avoids the sum. In languages with unbounded integers the issue does not arise. This is a well-known real bug, so it is worth knowing.
What each one costs
Because binary search halves the range, the number of looks is about log base 2 of n. Put another way: double the list and linear search does twice the work, while binary search does just one more look. That difference is why the method matters for big collections.
| List size | Linear search (up to) | Binary search (about) |
|---|---|---|
| 1,000 items | 1,000 looks | 10 looks |
| 1,000,000 items | 1,000,000 looks | 20 looks |
- 1,000,000looks at worst for linear search
- 20looks at worst for binary search
Expert viewComplexity summary
Binary search: best case O(1) (the middle item is the target), worst and average O(log n), extra space O(1) for the loop version. The recursive version uses O(log n) stack space. Each doubling of the list adds just one extra look. Linear search: O(1) best, O(n) average and worst, O(1) space. If the data must be sorted first, a comparison sort costs O(n log n) once, which is why the next section matters.
Does sorting first pay off?
Sorting costs work. It pays off when you search more than a few times.
- One search onlyJust use linear search: sorting would cost more than it saves
- Many searchesSort once, then each search is O(log n)
- Data changes a lotKeeping it sorted has a cost too: weigh insertions against searches
- Rule of thumbThe more searches per change, the more sorting pays
Expert viewBreak-even thinking
Linear search costs about n per query; sorted data costs about n log n once plus about log n per query. For n = 1,000,000 the one-off sort is on the order of tens of millions of steps, so it pays for itself after a few dozen searches. The exact point depends on constants, so measure. Sorted data that changes often needs a structure that keeps order cheaply, such as a balanced tree, rather than re-sorting an array.
Where you meet binary search
- Sorted filesFinding a record in a file kept in key order
- Database indexesIndexes keep keys in order so lookups need few steps (many use tree structures built on the same halving idea)
- Guessing gamesGuess a number from 1 to 100: seven guesses always suffice
- Version huntingFinding which change in an ordered history first broke something
Expert viewBinary search on answers
The same halving works when there is no list at all, as long as you can test a candidate answer and the result changes from "no" to "yes" exactly once as the candidate increases (a monotonic condition). Examples: the smallest capacity that fits a job, or the first version that fails a test. Search the range of possible answers, test the middle, and discard half. The cost is O(log of the range size) tests.
When linear is the better choice
- Unsorted dataNo ordering, no binary search
- One-off searchSorting costs more than the search saves
- Tiny listsA handful of items: overhead outweighs savings
- Linked listsNo jumping to the middle, so halving does not help
Expert viewPractical notes
For small n, the simpler loop can be as fast or faster because of low overhead and predictable memory access. With duplicates, plain binary search returns some matching position; finding the first or last match needs a small variation that keeps searching after a hit. Prefer your language's standard library search where it exists, and check its documentation for how it handles duplicates and missing items.
Try it by hand
- Lay out 3, 8, 12, 19, 27, 41, 56Face up, in order
- Linear: find 41Count the cards you touch (six)
- Binary: find 41Start at the middle card, discard half each time
- Write low, high, midUpdate them after each look
- Search for 20How do you know it is absent?
Halving is powerful, but only on data that is already in order.
Frequently asked questions
Why does binary search need sorted data?
Each look discards half the list on the assumption that order tells you which half. Without order, that assumption is false.
How many looks does binary search need for a billion items?
About 30, since 2 to the 30th is a little over a billion.
Is binary search always faster than linear?
Not always. On tiny lists or data you must sort first for one search, linear can win.
What if the item is not there?
Both methods end with a clear "not found": linear after the last item, binary when low passes high.