Difference between revisions of "Binary search"

From PEGWiki
Jump to: navigation, search
m (Possible bugs)
Line 67: Line 67:
  
 
===Possible bugs===
 
===Possible bugs===
One obvious bug is absentmindedly setting <code>r = n-1</code> initially. Doing this will prevent the value <code>n</code> from ever being returned, which renders the implementation correct whenever the answer is less than <code>n</code>, but incorrect whenever it is <code>n</code>. (It will simply return <code>n-1</code> in this case.)
+
As suggested below, the programmer has at least six opportunities to err.
 +
# Setting <code>r = n-1</code> initially. Doing this will prevent the value <code>n</code> from ever being returned, which renders the implementation correct whenever the answer is less than <code>n</code>, but incorrect whenever it is <code>n</code>. (It will simply return <code>n-1</code> in this case.)
 +
# Using <code>while (l &lt;= r)</code> instead of <code>while (l &lt; r)</code>. This will always cause an infinite loop in which the <code>else</code> branch is taken in every subsequent iteration.
 +
# Comparing <code>A[m]</code> with <code>c</code> in the wrong direction, that is, writing <code>A[m] &gt; c</code>, <code>A[m] &gt;= c</code>, <code>c &lt; A[m]</code>, or <code>c &lt;= A[m]</code>, or reversing the order of the two branches. This would not correspond to the theory, and would almost always given an incorrect result. Note that simultaneously logically negating the comparison and reversing the order of the branches, however, will not give an error, but will instead give logically equivalent code.
 +
# Computing <code>m</code> as the ceiling of the arithmetic mean, instead of the floor. The obvious error condition here is that when <code>l == n-1</code> and <code>r == n</code>, the value of <code>m</code> computed will be <code>n</code>, and we will then attempt to examine a nonexistent element in the array, which could cause the program to crash.
 +
# Setting <code>l = m</code> or <code>l = m-1</code> instead of <code>l = m+1</code>. Either variation lends itself to an error condition in which <code>m</code> comes out to be equal to either <code>l</code> or <code>l+1</code>, respectively, and the first branch is taken, which causes an infinite loop in which the first branch is ''always'' taken.
 +
# Setting <code>r = m+1</code> or <code>r = m-1</code> instead of <code>r = m</code>. In the former case, we could have an infinite loop in which the second branch is always taken, if the difference between <code>l</code> and <code>r</code> is 1 or 2. In the latter case, it is possible for <code>r</code> to become less than <code>l</code>.
 +
And, of course, one can easily mix up the <code>upper_bound</code> and <code>lower_bound</code> implementations, giving a seventh opportunity to err.
  
Another obvious bug is using <code>while (l &lt;= r)</code> instead of <code>while (l &lt; r)</code>. This will always cause an infinite loop in which the <code>else</code> branch is taken in every subsequent iteration.
+
Additionally, if the array can be very large, then <code>m</code> should be computed as <code>l + (r-l)/2</code>, instead of <code>(l+r)/2</code>, in order to avoid possible arithmetic overflow.
  
A third obvious bug is either comparing <code>A[m]</code> with <code>c</code> in the wrong direction, that is, writing <code>A[m] &gt; c</code>, <code>A[m] &gt;= c</code>, <code>c &lt; A[m]</code>, or <code>c &lt;= A[m]</code>, or reversing the order of the two branches. This would not correspond to the theory, and would almost always given an incorrect result.
+
==Discrete: function==
 +
More generally, we have some monotone function <math>f</math> which is easy to compute, and we need to compute its inverse, which, on the face, seems to be tricky. It is also not immediately obvious that we can make this abstraction from a given problem, but once the abstraction is discovered, a simple and efficient solution to the problem immediately follows.
  
However, there are still four degrees of freedom in the implementation:
+
The example problem we will consider is... TODO.
# Should we compute <code>m</code> as the floor of the arithmetic mean of <code>l</code> and <code>r</code>, or as the ceiling?
+
 
# Should we compare <code>A[m]</code> with <code>c</code> strictly, that is, with <code>&lt;</code>, or non-strictly, that is, with <code>&lt;=</code>?
+
==Continuous==
# Should we set <code>l = m+1</code>, <code>l = m</code>, or <code>l = m-1</code> in the first branch?
+
TODO
# Should we set <code>r = m+1</code>, <code>r = m</code>, or <code>r = m-1</code> in the second branch?
+
 
These variations are covered in the page [[Binary search/Implementation details]].
+
[[Category:Incomplete]]

Revision as of 08:47, 1 January 2012

Binary search is the term used in computer science for the discrete version of the bisection method, in which given a monotone function f over a discrete interval I and a target value c one wishes to find x \in I for which f(x) \approx c. It is most often used to locate a value in a sorted array. The term may also be used for the continuous version.

Discrete: array

In the most commonly encountered variation of binary search, we are given a zero-indexed array A of size n that is sorted in ascending order, along with some value c. Here the domain of the function f is the set of indices into the array, and f(i) = A_i where A_i is the element at the ith position. There are two slightly different variations on what we wish to do:

  • Lower bound: Here are two equivalent formulations:
  1. Find the first index into A where we could insert a new element of value c without violating the ascending order.
  2. If there is an element in A with value greater than or equal to c, return the index of the first such element; otherwise, return n. In other words, return \min\{i\,|\,A_i \geq c\}, or n if that set is empty.
  • Upper bound:
  1. Find the last index into A where we could insert a new element of value c without violating the ascending order.
  2. If there is an element in A with value strictly greater than to c, return the index of the first such element; otherwise, return n. In other words, return \min\{i\,|\,A_i > c\}, or n if that set is empty.

The following properties then hold:

  • If there is no i such that A_i = c, then the lower bound and upper bound will be the same; they will both point to the first element in A that is greater than c.
  • If c is larger than all elements in A, then the lower and upper bounds will both be n.
  • If there is at least one element A with value c, then the lower bound will be the index of the first such element, and the upper bound will be the index of the element just after the last such element. Hence [lower bound, upper bound) is a half-open interval that represents the range of indices into A that refer to elements with value c.
  • The element immediately preceding the lower bound is the last element with value less than c, if this exists, or the hypothetical element at index -1, otherwise.
  • The element immediately preceding the upper bound is the last element with value less than or equal to c, if this exists, or the hypothetical element at index -1, otherwise.

Both lower bound and upper bound can easily be found by iterating through the array from beginning to end, which takes O(n) comparisons and hence O(n) time if the elements of the array are simple scalar variables that take O(1) time to compare. However, because the array is sorted, we can do better than this. We begin with the knowledge that the element we seek might be anywhere in the array, or it could be "just past the end". Now, examine an element near the centre of the array. If this is less than the element we seek, we know the element we seek must be in the second half of the array. If it is greater, we know the element we seek must be in the first half. Thus, by making one comparison, we cut the range under consideration into half. It follows that after O(\log n) comparisons, we will be able to locate either the upper bound or the lower bound as we desire.

Implementation

However, implementation tends to be tricky, and even experienced programmers can introduce bugs when writing binary search. Correct reference implementations are given below in C:

/* n is the size of the int[] array A. */
int lower_bound(int A[], int n, int c)
{
    int l = 0;
    int r = n;
    while (l < r)
    {
        int m = (l+r)/2;     /* Rounds toward zero. */
        if (A[m] < c)
            l = m+1;
        else
            r = m;
    }
    return l;
}
 
int upper_bound(int A[], int n, int c)
{
    int l = 0;
    int r = n;
    while (l < r)
    {
        int m = (l+r)/2;
        if (A[m] <= c)       /* Note use of < instead of <=. */
            l = m+1;
        else
            r = m;
    }
    return l;
}

Proof of correctness

We prove that lower_bound above is correct. The proof for upper_bound is very similar.

We claim the invariant that, immediately before and after each iteration of the while loop:

  1. The index we are seeking is at least l.
  2. The index we are seeking is at most r.

This is certainly true immediately before the first iteration of the loop, where l = 0 and r = n. Now we claim that if it is true before a given iteration of the loop, it will be true after that iteration, which, by induction, implies our claim. First, the value m will be exactly the arithmetic mean of l and r, if their sum is even, or it will be 0.5 less than the mean, if their sum is odd, since m is computed as the arithmetic mean rounded down. This implies that, in any given iteration of the loop, m's initial value will be at least l, and strictly less than r. Now:

  • Case 1: A[m] < c. This means that no element with index between l and m, inclusive, can be greater than c, because the array is sorted. But because we know that such an element exists (or that it is the hypothetical element just past the end of the array) in the current range delineated by indices l and r, we conclude that it must be in the second half of the range with indices from m+1 to r, inclusive. In this case we set l = m+1 and at the end of the loop the invariant is again satisfied. This is guaranteed to increase the value of l, since m starts out with value at least l. It also does not increase l beyond r, since m is initially strictly less than m.
  • Case 2: A[m] >= c. This means that there exists an element with index between l and m, inclusive, which is at least c. This implies that the first such element is somewhere in this half of the range, because the array is sorted. Therefore, after setting r = m, the range of indices between l and r, inclusive, will still contain the index we are seeking, and hence the invariant is again satisfied. This is guaranteed to decrease the value of r, since m starts out strictly less than r; it also will not decrease it beyond l, since m starts out at least as large as l.

Since each iteration of the loop either increases l or decreases r, the loop will eventually terminate with l = r. Since the invariant still holds, this unique common value must be the solution. _{\blacksquare}

Carefully proving the O(\log n) time bound and showing the correctness of upper_bound are left as exercises to the reader.

Possible bugs

As suggested below, the programmer has at least six opportunities to err.

  1. Setting r = n-1 initially. Doing this will prevent the value n from ever being returned, which renders the implementation correct whenever the answer is less than n, but incorrect whenever it is n. (It will simply return n-1 in this case.)
  2. Using while (l <= r) instead of while (l < r). This will always cause an infinite loop in which the else branch is taken in every subsequent iteration.
  3. Comparing A[m] with c in the wrong direction, that is, writing A[m] > c, A[m] >= c, c < A[m], or c <= A[m], or reversing the order of the two branches. This would not correspond to the theory, and would almost always given an incorrect result. Note that simultaneously logically negating the comparison and reversing the order of the branches, however, will not give an error, but will instead give logically equivalent code.
  4. Computing m as the ceiling of the arithmetic mean, instead of the floor. The obvious error condition here is that when l == n-1 and r == n, the value of m computed will be n, and we will then attempt to examine a nonexistent element in the array, which could cause the program to crash.
  5. Setting l = m or l = m-1 instead of l = m+1. Either variation lends itself to an error condition in which m comes out to be equal to either l or l+1, respectively, and the first branch is taken, which causes an infinite loop in which the first branch is always taken.
  6. Setting r = m+1 or r = m-1 instead of r = m. In the former case, we could have an infinite loop in which the second branch is always taken, if the difference between l and r is 1 or 2. In the latter case, it is possible for r to become less than l.

And, of course, one can easily mix up the upper_bound and lower_bound implementations, giving a seventh opportunity to err.

Additionally, if the array can be very large, then m should be computed as l + (r-l)/2, instead of (l+r)/2, in order to avoid possible arithmetic overflow.

Discrete: function

More generally, we have some monotone function f which is easy to compute, and we need to compute its inverse, which, on the face, seems to be tricky. It is also not immediately obvious that we can make this abstraction from a given problem, but once the abstraction is discovered, a simple and efficient solution to the problem immediately follows.

The example problem we will consider is... TODO.

Continuous

TODO