Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

# Invariants for Binary Search, Part 3: Improving Our Abstractions

October 31, 2014

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 `true` if

• `k` is the position of an element of the sequence that is not (strictly) less than `x`, or
• `k` is equal to `n` (i.e., `k` is the off-the-end position).

Otherwise, `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
```

Because `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 `n`.

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 `vless` that accepts a value `x` and an index `k` in the range `[0, n]`.
• The value of `vless(x, n)` is `true`.
• All of the `false` results of `vless(x, k)` come before all of the `true` results. That is, if `vless(x, i)` is `false` and `vless(x, j)` is `true`, then `i < j`.
• Our problem is to find the lowest value of `k` such that `vless(x, k)` is `true`.

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.

### More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.