Section 26.2 Binary Search
Consider searching a list of value that you know to be in order:
4, 12, 34, 38, 56, 72, 91, ...
How might you modify the linear search strategy given this information?
Say you were searching for the value 42. Once you saw 56, you could stop searching because you know 42 is not in the list.
Or, if you were searching for a value you expected to be near the end of the list (say the name "Zoe" in an alphabetical list of names), you could start searching from the end and move backwards through the list.
Both of these strategies might help in some cases. But in general, we can’t guarantee they will be more efficient. If we guess wrong about which end the value is likely to be at, we might still end up searching the entire list.
But there is a better way to take advantage of the fact that the list is ordered. This method is called binary search. Binary search works by repeatedly dividing the list in half, and determining which half the desired value must be in. This halving process continues until either the value is found, or the list cannot be divided any further.
We don’t truly divide the list in two. If we are searching a vector, we do not break it into two vectors. Instead, we keep track of the range of indices that we are currently considering. Initially, this range is the entire list. We then look at the middle element of the current range. If that element is the one we are looking for, we are done. If the middle element is less than the one we are looking for, we know that the desired element must be in the upper half of the current range (if it is present at all). So we update our range to be just the upper half. If the middle element is greater than the one we are looking for, we update our range to be just the lower half. We repeat this process until we either find the desired element or our range is empty.
Give it a try in the activity below. It tracks the current range using
lowIndex and highIndex. Initially, they are set to 0 and 9 respectively as those are the first and last indexes in the list. We then calculate the middle index of that range by adding the two indexes and dividing by 2 (rounding down if necessary). That is the value we look at and compare to our key. If it is not what we are looking for, we update either the low index or the high index:
Note that there are three possible outcomes when we check the middle index:
-
It has the key and we can stop.
-
The value there is too low, so we update the low index to be one more than the middle index. This excludes the value we just checked and everything below it.
-
The value there is too high, so we update the high index to be one less than the middle index. This excludes the value we just checked and everything above it.
Insight 26.2.1.
With each step of the algorithm, only one index (low or high) changes. We either learn that the value must be in the top half of the remaining range (and thus the low index must change), or it must be in the bottom half (and thus the high index must change).
If the low index ever becomes greater than the high index, it means the key is not present in the list.
Now try doing a binary search yourself:
Activity 26.2.2. A Binary Search Quiz.
Click the middle location in the list during each step of the binary search.
If you do not get a perfect score, you can use Reset to try again.
Implemented to search a vector in C++, it looks like this:
Checkpoint 26.2.1.
Checkpoint 26.2.2.
Checkpoint 26.2.3.
You have attempted of activities on this page.
