Shamim Hafiz - 7 months ago 38

C 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

`lower_bound`

is almost like doing a usual binary search, except:

- If the element isn't found, you return your current place in the search, rather than returning some null value.
- 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. :-)