Shamim Hafiz Shamim Hafiz - 1 year ago 179
C Question

Implementation of C lower_bound

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 Source

lower_bound is almost like doing a usual binary search, except:

  1. If the element isn't found, you return your current place in the search, rather than returning some null value.
  2. If the element is found, you search leftward until you find a non-matching element. Then you return a pointer/iterator to the first matching element.

Yes, it's really that simple. :-)

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download