A. Programming Concepts and Skills · Algorithm Design and Analysis

Linear versus Binary Search: Run Times and Complexity

C2.2 A3.2About 70 minutes

Learning goals

I can compare linear and binary search by counting comparisons for the best, worst and average cases.
I can design a fair run-time experiment and explain its results with Big-O.
I can decide when sorting first and then using binary search is worth the cost.
I can explain the other factors in choosing a search: data size, how often it changes, and how it is stored.

Words to know

empirical analysis
Studying an algorithm by running it and measuring (run times or counted steps).

theoretical analysis
Studying an algorithm by reasoning about its step count as a function of n (for example with Big-O).

break-even point
The input size or number of uses at which two approaches cost the same; beyond it one becomes cheaper.

random access
Reading any element directly by its index in O(1), as with arrays and Python lists. Binary search needs it.

amortize
To spread a one-time cost (such as sorting) over many later operations.

The 2.5-second search

A program searches a list of a million sorted numbers 100 times. With linear search it takes about 2.5 seconds. With binary search, about half a millisecond: roughly 5000 times faster. Both are correct. In this lesson you will predict that difference before running anything, measure it carefully, and learn when the faster algorithm is not the better choice.

Theory first: counting comparisons

From the last two lessons (n elements, target equally likely to be any element):

Case	Linear search	Binary search
Best	1 comparison (first element)	1 pass (middle element)
Worst	n	about log₂ n + 1 (the number of binary digits of n)
Average (successful)	(n + 1) ÷ 2	a little less than the worst case
Unsuccessful	n	about log₂ n + 1
Big-O (worst)	O(n)	O(log n)
Precondition	none on order	sorted by the key; random access

Each binary search pass compares the target with a[mid] (one or two comparisons in code; the Big-O is the same either way).

Checking the theory with a counting experiment

The program below searches for every element of a sorted list once, counts comparisons (passes, for binary search) and prints the average and the maximum.

def linear_count(a, target):

count = 0

for v in a:

count += 1

if v == target:

break

return count

def binary_count(a, target):

count = 0

low, high = 0, len(a) - 1

while low <= high:

count += 1

mid = (low + high) // 2

if a[mid] == target:

break

elif a[mid] < target:

low = mid + 1

else:

high = mid - 1

return count

print("n linear avg binary avg linear max binary max")

for n in [15, 100, 1000, 10000]:

a = list(range(n))

lin = [linear_count(a, t) for t in a]

bin_ = [binary_count(a, t) for t in a]

print(f"{n:<8}{sum(lin)/n:<12.1f}{sum(bin_)/n:<12.1f}{max(lin):<12}{max(bin_)}")

Output, one line each: n linear avg binary avg linear max binary max, 15 8.0 3.3 15 4, 100 50.5 5.8 100 7, 1000 500.5 9.0 1000 10, 10000 5000.5 12.4 10000 14. Both programs search for the same targets. Linear search's average is exactly (n + 1) ÷ 2. Binary search's maximum is the number of binary digits of n (4 for 15, 14 for 10 000), and its average is only one or two less.

Worst-case comparisons as n grows. Linear search grows in a straight line; binary search climbs one step each time n reaches a power of 2 (1, 2, 4, 8, 16, 32, 64), and is only at 7 when n = 64.

Measuring run times fairly

Now measure real time. A fair experiment:

uses the same data and the same targets for both algorithms;
includes both present and missing targets (here, random numbers, about half of which are odd and so missing from a list of even numbers);
repeats each search many times, so each measurement is not tiny and noisy;
grows n by a fixed factor (×10) so you can see the pattern, not just one number.

import time, random, bisect

def linear_search(a, target):

for i in range(len(a)):

if a[i] == target:

return i

return -1

def binary_search(a, target):

low, high = 0, len(a) - 1

while low <= high:

mid = (low + high) // 2

if a[mid] == target:

return mid

elif a[mid] < target:

low = mid + 1

else:

high = mid - 1

return -1

random.seed(1)

for n in [10_000, 100_000, 1_000_000]:

a = list(range(0, 2 * n, 2)) # sorted even numbers

targets = [random.randrange(2 * n) for _ in range(100)]

for search in (linear_search, binary_search):

start = time.perf_counter()

for t in targets:

search(a, t)

ms = (time.perf_counter() - start) * 1000

print(n, search.__name__, round(ms, 2), "ms")

Your times will differ. On one computer the output was: linear search 28.63 ms, 243.88 ms and 2525.03 ms for n = 10 000, 100 000 and 1 000 000; binary search 0.17 ms, 0.26 ms and 0.5 ms.

Reading the results

Linear search: each ×10 in n multiplied the time by about 9 to 10. That is the signature of O(n).
Binary search: each ×10 in n added only a little time (log₂ of 10 is about 3.3, so about 3 or 4 more passes). That is O(log n). With such small times, noise also matters: rerun it and the smallest numbers will jump around.
The ratio grows with n: about 170 times faster at 10 000, about 5000 times faster at a million. Complexity analysis predicts exactly this: n ÷ log₂ n keeps growing.

Worked example

Is sorting first worth it?

You have an unsorted list of n = 1 000 000 numbers. Sorting it with an O(n log n) sort (such as merge sort, later in this unit) costs about n log₂ n ≈ 20 000 000 comparisons. After sorting, each binary search costs about 20 comparisons. A linear search on the unsorted list costs about 500 000 comparisons on average (successful searches). How many searches k make sorting worthwhile?

Cost of k linear searches: 500 000k.
Cost of sorting, then k binary searches: 20 000 000 + 20k.
Sorting wins when 20 000 000 + 20k < 500 000k, that is when 20 000 000 < 499 980k, so k > 40.002.
So from 41 searches on, sorting first is cheaper, and the gap keeps growing: 1000 searches cost 500 000 000 comparisons linearly, but only 20 020 000 with sort + binary search.
If you only search once or twice, do not sort: one linear search (500 000) is far cheaper than sorting (20 000 000).

About 41 or more searches. With few searches, linear search on the unsorted data is cheaper; with many, the one-time sort is amortized over all the fast binary searches.

Other things that decide the choice

Small n: for a list of 20 names, either search is instant. Simple, obviously-correct linear search is often the better engineering choice.
Data that changes often: keeping a list sorted means each insertion or deletion shifts up to n elements, O(n) (next lesson). If you insert far more often than you search, an unsorted list plus linear search may be cheaper overall.
Storage: binary search needs random access (jump straight to a[mid]). Data you can only read in order, such as a linked list (studied in university data-structures courses) or a stream from a network, must be searched linearly.
Something faster still: Python's set and dict use hash tables, which find a key in O(1) time on average. You will meet them again in first-year university courses; they are why x in my_set is so much faster than x in my_list for large data.

A decision guide for choosing a search. The "sort once, then binary search" branch pays off when the number of searches is larger than about 2 log₂ n (the break-even from the worked example), and when the data does not change constantly.

Just for fun

A linear search of Canada's more than 16 million homes for a lost cat could take 16 million knocks on doors.

A binary search would need only about 24 knocks, if the homes were sorted by cat. (Sadly, cats refuse to be sorted.)

Hands-on activity

Race the searches

You need: a computer with Python, and paper for a table.

Run the counting program from the lesson for n = 15, 100, 1000 and 10 000. Copy the table. Then add n = 100 000 (be patient: it can take a couple of minutes, because searching for every element makes about 5 × 10⁹ linear-search comparisons).
Run the timing program. Record the times in a table with columns n, linear (ms), binary (ms), linear ÷ binary.
Run it three times and keep the smallest time for each cell. Do the numbers still show linear growing about ×10 per row and binary growing only a little?
Change the targets so that all of them are missing (use odd numbers only: random.randrange(n) * 2 + 1). Predict first: will linear search get faster or slower? Why?
Write two or three sentences of conclusion using the words worst case, O(n) and O(log n).

What to look for: with all-missing targets, linear search becomes slower (always n comparisons, the worst case) while binary search hardly changes.

Your turn

For n = 2000, give the worst-case comparisons for linear search and the maximum number of passes for binary search.

Linear search takes 3 ms on 50 000 elements. Estimate the time for 500 000 elements and explain.

Binary search takes about 16 passes for n = 50 000. About how many for n = 100 000? For n = 50 000 × 1024?

Give two situations in which linear search is the better choice even though it is O(n).

Why must a fair timing experiment use the same targets for both searches?

What does "empirical" analysis mean, and what is the other kind?

More practice: warm-up

Which search needs sorted data?

Which search has O(n) worst case? Which has O(log n)?

Average comparisons for a successful linear search of 201 elements?

Maximum binary search passes for n = 255? For n = 256?

What is random access?

More practice: on your own

A list grows from 1000 to 1 000 000 elements. By what factor does the worst-case work grow for each search?

Times for a search were 4 ms, 4.5 ms and 5 ms for n = 10⁴, 10⁵ and 10⁶. Which search is it likely to be, and why?

Using the worked example's numbers, how many comparisons do 10 searches cost each way? Which is better?

A contacts app keeps 300 names sorted and searches them each time you type a letter. Is binary search worth programming here? Discuss.

Explain why x in my_list inside a loop over 100 000 items can be slow, and what built-in structure fixes it.

Challenge

Find the break-even number of searches in general: sorting costs n log₂ n, each binary search costs log₂ n, and each linear search costs n ÷ 2 (ignore the +1). Show that sorting is worth it once k is more than about 2 log₂ n.

A sorted list has 10⁹ elements. Linear search does 10⁸ comparisons per second and binary search's passes take the same time each. Estimate the worst-case time of each.

Interpolation search guesses the position from the values (like opening a dictionary near the back for "w"): pos = low + (target - a[low]) * (high - low) // (a[high] - a[low]). When is it faster than binary search, and when much slower?

Check your understanding

Quiz

For n = 1 000 000, which pair is closest to the worst-case comparisons of linear and binary search?

A search's time grows from 2 ms to 20 ms to 200 ms as n goes 10⁴, 10⁵, 10⁶. What does this suggest?

Why should a timing experiment repeat each search many times?

An unsorted list of a million items will be searched once. What is the best plan?

Which of these makes binary search impossible?

About how many searches make "sort first, then binary search" pay off for n = 1 000 000?

For parents and teachers

Big idea: C2.2 asks students to compare the efficiency of linear and binary search using run times and computational complexity analysis (counting statements, loop iterations or comparisons). This lesson does both, and shows that the theory predicts the measurements. It also uses the A3.2 algorithms built in the last two lessons.

How to help: Ask your teen to show you the timing table and explain the pattern in one sentence ("when n gets 10 times bigger, linear takes 10 times longer, but binary only takes a few steps more"). The decision guide is also a good conversation starter: "When would you not sort?"

Common difficulties:

Drawing conclusions from one noisy timing run.
Forgetting the cost of sorting when recommending binary search.
Thinking O(log n) means "half the time of O(n)": the gap grows enormously as n grows.
Comparing algorithms on different data or targets.