Binary Search
Consider a list of 1 million sorted values. Linear search starts at the beginning of the list and asks, “Is this value what I’m looking for?” If it isn’t, the same is asked about the second value, and then the third. Up to 1 million questions are asked. This algorithm doesn’t take advantage of the list being sorted.
Binary search is much faster than linear search, but requires a sorted list
Here’s a new algorithm, called binary search, that relies on the list being sorted. Look at the middle value and ask, “Is this value bigger than or smaller than the one I’m looking for?” With that one question, you can eliminate 500,000 values! That leaves a list of 500,000 values to search. Let’s do it again: look at the middle value, ask the same question, and eliminate another 250,000 values. You have eliminated 3/4 of the list with only two questions! Asking only 20 questions, you can locate a particular value in a list of 1 million sorted values.
To determine how fast it is, let’s consider the size of a list that can be searched with a certain number of questions. With only one question, you can determine whether a list of length 1 contains a value. With two questions, you can search a list of length 2. With three questions, you can search a list of length 4. Four questions, length 8. Five questions, length 16. Every time you ask another question, you can search a list twice as large.
Using logarithmic notation, N sorted values can be searched in ceil(log2N) steps, where ceil is the ceiling function that rounds a value up to the nearest integer. As shown in Table 11, , this increase is significantly slower than the time required for linear search.
| Searching N Items | Worst Case—Linear Search | Worst Case—Binary Search |
|---|---|---|
| 100 | 100 | 7 |
| 1000 | 1000 | 10 |
| 10,000 | 10,000 | 14 |
| 100,000 | 100,000 | 17 |
| 1,000,000 | 1,000,000 | 20 |
| 10,000,000 | 10,000,000 | 24 |
The key to binary search is to keep track of three parts of the list: the left part, which contains values that are smaller than the value you are searching for; the right part, which contains values that are equal to or larger than the value you are searching for; and the middle part, which contains values that you haven’t yet examined—the unknown section. If there are duplicate values, you will return the index of the leftmost one, which is why the “equal to” section belongs on the right.
Let’s use two variables to keep track of the boundaries: i will mark the index of the first unknown value, and j will mark the index of the last unknown value:
At the beginning of the algorithm, the unknown section comprises the entire list, so set i to 0 and j to the length of the list minus one:
You are done when that unknown section is empty—when you’ve examined every item in the list, which happens when i == j + 1—when the values cross. (When i == j, there is still one item left in the unknown section.) Here is a picture of what the values are when the unknown section is empty:
To make progress, set either i or j to near the middle of the range between them. Let’s call this index m, which is at (i + j) // 2. (Notice the use of integer division: you are calculating an index, so you need an integer.)
Think for a moment about the value at m. If it is less than v, you need to move i up, while if it is greater than v, you should move j down. But where exactly do you move them?
When you move i up, you don’t want to set it to the midpoint exactly, because L[m] isn’t included in the range; instead, set it to one past the middle—in other words, to m + 1.
Similarly, when you move j down, move it to m - 1:
The completed function is as follows:
| | from typing import Any |
| | |
| | def binary_search(L: list, v: Any) -> int: |
| | """Return the index of the first occurrence of value in L, or return |
| | -1 if value is not in L. |
| | |
| | >>> binary_search([1, 3, 4, 4, 5, 7, 9, 10], 1) |
| | 0 |
| | >>> binary_search([1, 3, 4, 4, 5, 7, 9, 10], 4) |
| | 2 |
| | >>> binary_search([1, 3, 4, 4, 5, 7, 9, 10], 5) |
| | 4 |
| | >>> binary_search([1, 3, 4, 4, 5, 7, 9, 10], 10) |
| | 7 |
| | >>> binary_search([1, 3, 4, 4, 5, 7, 9, 10], -3) |
| | -1 |
| | >>> binary_search([1, 3, 4, 4, 5, 7, 9, 10], 11) |
| | -1 |
| | >>> binary_search([1, 3, 4, 4, 5, 7, 9, 10], 2) |
| | -1 |
| | >>> binary_search([], -3) |
| | -1 |
| | >>> binary_search([1], 1) |
| | 0 |
| | """ |
| | |
| | # Mark the left and right indices of the unknown section. |
| | i = 0 |
| | j = len(L) - 1 |
| | |
| | while i != j + 1: |
| | m = (i + j) // 2 # Find the middle |
| | if L[m] < v: |
| | i = m + 1 |
| | else: |
| | j = m - 1 |
| | |
| | if 0 <= i < len(L) and L[i] == v: |
| | return i |
| | return -1 |
| | |
| | if __name__ == '__main__': |
| | import doctest |
| | doctest.testmod() |
There are many tests because the algorithm is quite complicated, and it must be tested pretty thoroughly. These tests cover these cases:
- The value is the first item.
- The value occurs twice. You want the index of the first one.
- The value is in the middle of the list.
- The value is the last item.
- The value is smaller than everything in the list.
- The value is larger than everything in the list.
- The value isn’t in the list, but it is larger than some and smaller than others.
- The list has no items.
- The list has one item.
In Chapter 15, , you’ll learn a different testing framework that allows you to write tests in a separate Python file (thus making docstrings shorter and easier to read; only a couple of examples are necessary), and you’ll learn strategies for coming up with your own test cases.
Binary Search Running Time
Binary search is much more complicated to write and understand than linear search. Is it fast enough to make the extra effort worthwhile? To find out, you can compare it to list.index. As before, search for the first, middle, and last items in a list with about ten million elements, as shown in Table 12, .
| Case | list.index | binary_search | Ratio |
|---|---|---|---|
| First | 0.0080 | 0.0132 | 0.60 |
| Middle | 45.0905 | 0.0086 | 5239.77 |
| Last | 91.0210 | 0.0087 | 10503.28 |
The results are impressive. Binary search is several thousand times faster than its linear counterpart when searching through ten million items. Most importantly, if you double the number of items, binary search requires only one more iteration, whereas the time for list.index nearly doubles.
Note also that although the time taken for linear search grows in step with the index of the item found, there is no such pattern for binary search. Regardless of the item’s location, it takes the same number of steps.
Built-In Binary Search
The Python standard library’s bisect module includes binary search functions that are slightly faster than your binary search. The function bisect_left returns the index where an item should be inserted in a list to keep it in sorted order, assuming it is sorted to begin with. The function insort_left does the insertion.
The word left in the name signals that these functions find the leftmost (lowest index) position where they can perform their jobs; the complementary functions bisect_right and insort_right find the rightmost position.
There is one minor drawback to binary search: the algorithm assumes that the list is sorted, but sorting is time- and memory-intensive. You’ll see that next.
