Lesson 18 · Algorithms

Searching: linear and binary

Finding one number in a list sounds simple, and it is: check each item until you find it. But on a sorted list there is a much faster way. Step through a search for 42 in a sorted list of 16 numbers, first one by one, then with binary search, which looks at the middle and throws away half the list each time.

10 min10 steps5 questionsIntermediate

Fig 18 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01A linear search looks for a number that is not in a list of 500 items. How many items does it check?

Linear search can only stop early when it finds the target. If the target is missing, it has to check every one of the 500 items.

02What must be true about a list before you can use binary search on it?

Binary search compares with the middle item and then throws away one half. That only works if every item on the left is smaller and every item on the right is bigger, which means the list is sorted.

03About how many comparisons does binary search need, at most, to search a sorted list of 1,000,000 items?

Each comparison halves what is left, and you can halve a million only about 20 times before one item is left (2 to the power 20 is 1,048,576). That is why binary search is O(log n).

04A binary search uses while low < high instead of while low <= high. What goes wrong?

When low equals high there is still one item in play. With <, the loop ends before checking it, so searching [5] for 5 returns -1. This is a classic off-by-one bug.

05a is [3, 7, 11, 15, 19, 24, 28, 33, 38, 42, 47, 51, 56, 61, 67, 72]. What does bisect_left(a, 40) return, and what does it tell you?

bisect_left never says 'not found'. It returns where the value would be inserted to keep a sorted: index 9, just before 42. You must check i < len(a) and a[i] == 40 yourself; here a[9] is 42, so 40 is missing.

Key terms

Glossary

Linear search: Checking the items of a list one at a time, from the front, until the target is found or the list ends. O(n).
Binary search: Searching a sorted list by comparing with the middle item and throwing away the half that cannot contain the target. O(log n).
Sorted: In order, smallest first (or largest first). Binary search needs a sorted list.
Pointer (low, high, mid): A variable that holds a position in the list. low and high mark the part still in play; mid is the middle of it.
Floor division //: Python's division that rounds down to a whole number: 23 // 2 is 11.
O(log n): Work that grows with the number of times you can halve n. Doubling the list adds only one more step.
Off-by-one error: A bug where a loop or index is one too many or one too few, such as using < where <= was needed.
bisect: Python's built-in module for binary search on sorted lists; bisect_left(a, x) returns where x is or would go.

Fine print

Notes and sources

This binary search looks at no more than floor(log2 n) + 1 items, whether the target is there or not. For n = 16 that is 5; for n = 1,000,000 it is 20, because 2^19 = 524,288 is not more than a million but 2^20 = 1,048,576 is.
The drawing counts one comparison per item looked at. The code tests a[mid] == target and then a[mid] < target, so in Python terms that can be two tests per item; the count still grows as log n.
Python's 42 in a and a.index(42) are linear searches: they check the items from the front.
Sorting first costs time too (Python's list.sort is O(n log n)), so binary search pays off when you search the same sorted list many times.
In Python, low + high cannot overflow because int has no size limit. In languages with fixed-size integers, such as C or Java, mid = low + (high - low) / 2 (integer division there) avoids that bug; the Python form is low + (high - low) // 2.
bisect_left returns len(a) when the target is bigger than every item, so check i < len(a) before reading a[i].

Quiz Unlocks after the last step.