Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

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.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips 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.
 


Video