Invariants for Binary Search, Part 3: Improving Our Abstractions
Last week, we discussed a variant of binary search that we give an ordered sequence and a value to seek, and that returns the first (i.e., leftmost) position at which that value could be inserted in the sequence without disrupting the order of the sequence. As an example, consider this sequence:
3 6 7 11 12 12 12 15 17 18 23
As usual, we start numbering positions at zero, so, for example, 7 is at position 2. If we search this sequence for 7, we would like the result to be 2. If we search for 8, 9, 10, or 11, we would like the result to be 3. The reason is that we can insert any of these latter four values at position 3 without disrupting the sequence. We can also insert 11 at position 4, but 3 is the lowest such position.
Similarly, if we search for 12, we want the result to be 4. We could also insert 12 at position 5 or 6, but 4 is the first such position. Searching for 13, 14, or 15 should return 7, and so on. Finally, if we search for any value strictly greater than 23, the result should be 11. There is no element at position 11, of course, but nevertheless 11 is the lowest position at which we can insert a value greater than 23 while still maintaining order.
More generally, if the sequence has n elements, there are n+1 possible search results: any non-negative integer less than or equal to n. If you like, the result is in the range [0, n] rather than the more usual range [0, n). By implication, the result does not necessarily correspond to the index of any element. Therefore, when we are talking about indices, we must be careful about referring to "the element at position k," because, even though k might be an index of interest to us, there might not be an element at that position.
To make it easier for us to reason about this program, let's define an abbreviation:
vless(x, k) is
kis the position of an element of the sequence that is not (strictly) less than
kis equal to
kis the off-the-end position).
vless(x, k) is
false. The first of these conditions effectively extends the sequence with a sentinel element. In this case, that element is not really there, but we can think of it as being an element with a value so large that no matter what value
x has, the sentinel's value is larger.
Having defined this abbreviation, let's consider how it would apply to our example sequence. If we look at
vless(0, k) for all values of
k, we would get
T T T T T T T T T T T T
0 is less than each of the elements of our sequence, all the
vless values are
true. If we look at the values of
vless(12, k), we see
F F F F T T T T T T T T
because each of the first four elements of the sequence is strictly less than
12 and the others are not. The last
T is there because of the case where
k is equal to
Finally, if we look at
vless(12, k), we see
F F F F F F F F F F F T
because every element of the sequence is strictly less than
x, but the case where
k is equal to
n still gives us a
T at the end.
We have now reduced our binary-search problem to the following:
- We have a function
vlessthat accepts a value
xand an index
kin the range
- The value of
- All of the
vless(x, k)come before all of the
trueresults. That is, if
i < j.
- Our problem is to find the lowest value of
We have simplified our binary-search problem in some important ways.
First, although we did not talk about it this way earlier, we have effectively turned the search problem into a partitioning problem. We noted that
x is less than some elements of our sequence but not others, that these two kinds of elements form two contiguous subsequences (because the sequence is ordered), and that the result that we seek is the location of the boundary between the two subsequences. Thinking about the problem this way makes it possible to avoid the notion of "the element with value
x," which is good because such an element might not exist, or there might be more than one of them.
Next, we finessed the problem that not every position we inspect contains an element by defining a single function that behaves as if an element is there with an infinitely large value. This notion, which we called a sentinel, turns out to have enough other interesting applications that we shall discuss them separately later.
Finally, by defining our
vless abstraction, we managed to avoid having to tie our brains in knots asking "Did we mean that
x is less than the element at position
k, or less than or equal, or is it the other way around?" If we happen to have gotten things wrong when we defined
vless, at least we have done so only once, and we can fix it in a single place.
With this abstraction under our belts, we can proceed to write code. If you're interested, you might like to do so for yourself before I show you the details next week.