Binary Search to get position of first integer >= searched integer

Question

In a sorted array, I need to find the position of the first integer >= a given integer(-1 should be returned if no such integer exists in the array). Is the following modification of binary search correct to solve the problem? I have used quite a few test cases to verify the functionality, but still want to confirm.

n = no. of elements in the array

ele= integer to be searched

int binarySearch(int a[],int n,int ele)
{
  int lower=0;
  int upper=n-1;

  int mid;
  int pos=-1;
  while(lower<=upper)
  {
    mid=(lower+upper)/2;
    if (a[mid]==ele)
    {
        while(mid>=0 && a[mid]==ele)
            mid--;
        return mid+1;
    }
    else if(a[mid]<ele)
        lower=mid+1;
    else
    {
        pos=mid;
        upper=mid-1;
    }
  }
  return pos;
}

Answer 1

What you have written is not binary search; in the worst case, it is a linear search. (Consider what happens when the array contains all the same element).

Believe it or not, a normal binary search will do exactly what you want, (find the smallest integer that is greater than or equal to the target), given it is programmed correctly.

We can program it with the help of some invariants.

• 0 <= lo <= hi <= n
• a[0..lo) < x
• a[hi..n) >= x

where x is the target element and a[0..lo) <= x means that all the elements in the half open interval of [0..lo) are less than x.

lo and hi are the lower and upper bounds, and to begin with, they will be 0 and n which makes both the ranges in the invariant initially empty.

So now the algorithm:

int 
binarySearch(int a[], int n, int x)
{
    int lo = 0, hi = n;

    while(lo < hi)
    {
        int mid = lo + (hi - lo)/2;

        if(a[mid] < x) lo = mid + 1;
        else           hi = mid;
    }

    return hi;
}

So the body is just a standard binary search body, with the inclusion of the non-overflowing calculation of mid.

Deciding which of lo and hi should be assigned mid also follows pretty directly from the invariant:

• If a[mid] < x then a[mid] should be in the range a[0..lo) so lo = mid + 1.
• Conversely, if a[mid] >= x, then a[mid] belongs in a[hi..n) so hi = mid.

The return statement is also pretty self-explanatory, because given the invariant is true a[hi] is the smallest element in a satisfying a[i] >= x.

The last thing to look at then is the condition in the while loop, specifically, this loop will stop if lo >= hi which, considering the invariants, could only happen if lo = hi. at which point a[lo..hi) is empty, meaning the search space has been exhausted.

The interface for this implementation is slightly different from what you specified, because if there is no such element in the array, then it treats the range a[hi..n) as empty, which is true when hi = n. This means instead of returning -1, it returns n, which is just as easy to check, but if you want to make it return -1 just replace the return statement with this:

return hi < n ? hi : -1;