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 19 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:
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.
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).
