Implementation of C lower_bound

user_326820 0
Viewed 38562

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);

}
lower-bound binary-search c algorithm
8 Answers

C++ Implementation

int binary_search_lower_bound(vector<int>& array, int target) {
    int lo = 0, hi = (int)array.size();
    int mid;

    while(lo < hi) {
        mid = lo + ((hi - lo) >> 1);
        int val = array[mid];
        if (target <= val)//array[mid])
            hi = mid;
        else
            lo = mid + 1;
    }

    return lo;
}

Edit: Fixed bug for non-existing value.

user_57584720

Example if this is the given array

1 2 3 3 4

and different values of x is

3 then firstOccurance will be 2 and lastOccurance will be 3

2 then firstOccurance will be 1 and lastOccurance will be 1

10 then firstOccurance will be -1 and lastOccurance will be -1

int firstOccurance(vector<int>& arr, int x){
        int low = 0;
        int high = arr.size();
        int ans=-1;
        while(low<=high){
            int mid = (low+high)/2;
            if(arr[mid]==x)     ans=mid;
            if(arr[mid]>=x)     high=mid-1;
            else    low = mid+1;
        }
        return ans;
    }


int lastOccurance(vector<int>& arr, int x){
    int low = 0;
    int high = arr.size();
    int ans=-1;
    while(low<=high){
        int mid = (low+high)/2;
        if(arr[mid]==x)     ans=mid;
        if(arr[mid]<=x)     low=mid+1;
        else    high = mid-1;
    }
    return ans;
}
user_76579520

I know this is a very old post with a lot of answers already but I came across this problem as well and needed a generic solution so I used manish_s answer to adapt the gnu stdlib bsearch function. In case anyone needs it:

size_t myBsearch (const void *__key, const void *__base, size_t __nmemb, size_t __size,
         __compar_fn_t __compar)
{
  size_t __l, __u, __idx;
  const void *__p;
  int __comparison;
  __l = 0;
  __u = __nmemb;
  while (__l < __u)
    {
    __idx = (__l + __u) / 2;
    __p = (void *)(((const char *)__base) + (__idx * __size));
    __comparison = (*__compar)(__key, __p);
    if (__comparison <= 0)
      __u = __idx;
    else if (__comparison > 0)
      __l = __idx + 1;
    }
  return __l;
}
user_39197060
Related