Search code examples
c++algorithmbinary-searchinvariants

invariant of binary search for finding first occurrence of an element

I have a problem with defining the invariant of finding the first element of a binary search. (I have a sorted array a and I want to find the first element that is equal to some number q and if it does not exist return -1)

First, I set this invariant for my while.

My invariant

"Always a[l]<= q and also a[r] > q" ==> "Always l <= ind and also > ind".

Up to my invariant, I wrote this code:

int l=0,r=n;
while(l<r){
    int mid=(r+l)/2;
    if(a[mid]==q){
        r=mid+1;
    }
    else{
        if(a[mid]>q){
            r=mid;
        }else if(a[mid]<q) l=mid+1;
    }
}
return l;

But there is a problem that if(a[mid]==q) then I must pick an r that doesn't violate my invariant.

If I choose mid-1 I will violate it because a[r] will be <= q.

And I must iterate through my indices until I find an index I that a[i]>q and then set r to that index. (r=i)==>But If I do this it's not O(log n)

And I have seen some code implementing lower_bound that if(a[mid]==q) the set r to mid but I think they are violating they invariant but they code are correct and return the correct value.

Like this code:

1- int l = 0;
2- int r = n; // Not n - 1
3- while (l < r) {
4-     int mid = (l + r) / 2;
5-     if (q <= a[mid]) {
6-         r = mid;
7-     } else {
8-         l = mid + 1;
9-     }
10- }
11- return l;

At the first, The invariant is like my invariant(i is on the range of [l,r) ) but in line 5 consider if(q==a[mid]) then obviously it's violating because its( [l,r] because r is equal and it can be the first occurrence).

Am I right or I don't have the correct understanding concept of invariant?

Solution

  • Suppose we have a sequence

    ..., <q, <q, <q, q, q, ..., q, q, >q, >q, >q, ...
                 ^ (*)

    where <q (>q) stands for any element < q (> q). We want to find the point (*).

    We have two pointers, left < right. How can we use them to distinguish that point? The answer is simple: left should point to the last <q element, right should point to the first q element:

    ..., <q, <q, <q, q, q, ..., q, q, >q, >q, >q, ...
                 ^ right
             ^ left

    The invariant is: *left < q and *right >= q.

    The invariant that you suggested, *left <= q and *right > q corresponds to the last element in that sequence:

    ..., <q, <q, <q, q, q, ..., q, q, >q, >q, >q, ...
                                  ^ right
                               ^ left

    Some references that can be useful: