Binary search and invariant relation

Question

I'm reading this post and trying to figure out how could we determine invariant relation for binary search. To be specific, in the two examples he gave, why these two invariant relation is different? What make the different?

The part A[start] < target < A[end] is obvious, but the question is where to put the = sign?

Another question is, could I simply change the framework to:

int binarySearchFramework(int A[], int n, int target) {
    int start = start index of array - 1;
    int end = length of the A;
    while (end - start > 1) {
        int mid = (end - start) / 2 + start;
        if (A[mid] == target) return mid;
        if (A[mid] < target) {
            end = mid;
        } else {
            start = mid;
        }
    }      
   //not found
   ...
}  

Is this one not as good as the one provided in the post?

Thanks a lot!

Answer 1

You get to pick the invariant. It's a skill learned from practice. Even with experience, it usually involves some trial and error. Pick one. See how it goes. Look for opportunities to choose a different one that will require less work to maintain. The invariant you choose can make a significant difference in your code's complexity and/or efficiency.

There are at least four reasonable choices for invariant in a binary search:

a[lo] <  target <  a[hi]
a[lo] <= target <  a[hi]
a[lo] <  target <= a[hi]
a[lo] <= target <= a[hi]

You'll usually see the last one because it's the easiest to explain and doesn't involve tricky initialization with out-of-range array indices, which the others do.

Now there is a reason to use an invariant like a[lo] < target <= a[hi]. If you want always to find the first of a repeated series of the target, this invariant will do it O(log n) time. When hi - lo == 1, hi points to the first occurrence of the target.

int find(int target, int *a, int size) {
  // Establish invariant: a[lo] < target <= a[hi] || target does not exist
  // We assume a[-1] contains an element less than target. But since it is never
  // accessed, we don't need a real element there.
  int lo = -1, hi = size - 1;
  while (hi - lo > 1) {
    // mid == -1 is impossible because hi-lo >= 2 due to while condition
    int mid = lo + (hi - lo) / 2;  // or (hi + lo) / 2 on 32 bit machines
    if (a[mid] < target)
      lo = mid; // a[mid] < target, so this maintains invariant
    else
      hi = mid; // target <= a[mid], so this maintains invariant
  }
  // if hi - lo == 1, then hi must be first occurrence of target, if it exists.
  return hi > lo && a[hi] == target ? hi : NOT_FOUND;
}

NB this code is untested, but ought to work by the invariant logic.

The invariant with two <='s will only find some instance of the target. You have no control over which one.

This invariant does required initialization with lo = -1. This adds a proof requirement. You must show that mid can never be set to -1, which would cause out-of-range access. Fortunately this proof is not hard.

The article you cited is a poor one. It has several mistakes and inconsistencies. Look elsewhere for examples. Programming Pearls is a good choice.

Your proposed change is correct but may be a bit slower because it replaces a test that runs only one time with one that runs once per iteration.

Answer 2

The answer to your question is the answer to the question "What is a loop invariant".

The whole point of a loop invariant is to provide a useful property before, during, and (probably most importantly) after the termination of the loop. As an example, insertion sort has a loop invariant that the array to be sorted is in sorted order for a range that starts at 1 index (one item is always sorted), and grows to be the entire array. The usefulness of this is that if its true before the loop starts, and the loop doesn't violate it, you can infer correctly that after the execution of the loop the entire array is sorted. Assuming you didn't mess up your termination condition, which doesn't violate the loop invariant because the invariant only refers to a subarray of the entire array, which may or may not be the entire array. If you terminate early, the subarray is less than the entire array, but the subarray is guaranteed to be sorted, per the invariant.

The post you linked says much the same, though it would probably be better if the author actually explained more about what he was talking about. The article seems to seek to teach, yet leaves much unsaid that should be said, even if just as a footnote to more in-depth information for those who are curious or need more information.

To answer your question "why are the two invariants different" directly, the answer is because they are solving two different problems.

A couple of quotes from your link that illustrate this:

• I emphasize once again, the invariant relation guides us coding.
• Finding the invariant relation of the problem, and then everything becomes easy.

Answer 3

You wrote

The part A[start] < target < A[end] is obvious

but it's obviously wrong because initial values should be start = 0, end = N-1 (not -1, N). BTW, you don't need any invariant for the case described in your link (array of distinct elements).

This will work without problems and easy to understand.

int arr[] = {0,1,2,3,4,5,6,7};
int N = sizeof (arr) / sizeof (arr[0]);
int target = 4;

int l = 0, r = N-1;
while( l <= r ) {
    int mid = (l+r)>>1;
    if( arr[mid] == target )
        return mid;
    if( arr[mid] < target )
        l = mid + 1;
    else
        r = mid - 1;
}
return -1; // not found