Implementation of C lower_bound

Question

Based on the following definition found here

Returns an iterator pointing to the first element in the sorted range [first,last) which does not compare less than value. The comparison is done using either operator< for the first version, or comp for the second.

What would be the C equivalent implementation of lower_bound(). I understand that it would be a modification of binary search, but can't seem to quite pinpoint to exact implementation.

int lower_bound(int a[], int lowIndex, int upperIndex, int e); 

Sample Case:

int a[]= {2,2, 2, 7 };  lower_bound(a, 0, 1,2) would return 0 --> upperIndex is one beyond the last inclusive index as is the case with C++ signature.  lower_bound(a, 0, 2,1) would return 0.  lower_bound(a, 0, 3,6) would return 3; lower_bound(a, 0, 4,6) would return 3;  

My attempted code is given below:

int low_bound(int low, int high, int e) {     if ( low < 0) return 0;     if (low>=high )     {       if ( e <= a[low] ) return low;       return low+1;     }     int mid=(low+high)/2;     if ( e> a[mid])         return low_bound(mid+1,high,e);     return low_bound(low,mid,e);  } 

Answer 1

Here are the equivalent implementations of upper_bound and lower_bound. This algorithm is O(log(n)) in the worst case, unlike the accepted answer which gets to O(n) in the worst case.

Note that here high index is set to n instead of n - 1. These functions can return an index which is one beyond the bounds of the array. I.e., it will return the size of the array if the search key is not found and it is greater than all the array elements.

int bs_upper_bound(int a[], int n, int x) {     int l = 0;     int h = n; // Not n - 1     while (l < h) {         int mid =  l + (h - l) / 2;         if (x >= a[mid]) {             l = mid + 1;         } else {             h = mid;         }     }     return l; }  int bs_lower_bound(int a[], int n, int x) {     int l = 0;     int h = n; // Not n - 1     while (l < h) {         int mid =  l + (h - l) / 2;         if (x <= a[mid]) {             h = mid;         } else {             l = mid + 1;         }     }     return l; } 

The actual C++ implementation works for all containers. You can find it here.