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

}

If you look a bit lower on the page you linked, there's an implementation that you can study. — Matteo Italia, Jun 22 '11 at 16:54
The exact implementation is not specified by the C++ standard. — Lightness Races in Orbit, Jun 22 '11 at 16:56
@Space_C0wb0y: It probably is a show-me-teh-codez question. :-) — C. K. Young, Jun 22 '11 at 16:56
@Space: It's "make a C version of C++'s `std::lower_bound` for me kthx" — Lightness Races in Orbit, Jun 22 '11 at 16:56
@Tomalak: still, since the function requires a sorted range and the standard requires logarithmic complexity I don't think there are algorithms other than binary search that could be sensibly used. :) — Matteo Italia, Jun 22 '11 at 16:58
@Chris: Its not really a please do the code for me. I did make some attempt. But it was failing for some cases. — Shamim Hafiz - MSFT, Jun 22 '11 at 17:00
@Gunner: before the example, there's an example implementation, precisely after *The behavior of this function template is equivalent to:* If you change iterators with pointers and make some minor modification you get your C version. — Matteo Italia, Jun 22 '11 at 17:01
@Gunner: Then you should have posted that code in a question that asks "what did I do wrong here? why do I get this error in this case?" — Lightness Races in Orbit, Jun 22 '11 at 17:01
@Matteo: Oh yes. What a silly overlook :P. So far, this is the best answer I got :) — Shamim Hafiz - MSFT, Jun 22 '11 at 17:06
@Tomalak: I understand. I did understand why my code was failing, but I guess I should have posted that anyway to show my erroneous attempt. Maybe will edit post and add. — Shamim Hafiz - MSFT, Jun 22 '11 at 17:07
@Gunner: Posting the code does two things. First, it gives us a basis to recommend changes. Second, it shows that you're making an effort and that this isn't a "gimme teh codez" post, and it's much more pleasant to work with somebody than for somebody when not getting paid. — David Thornley, Jun 22 '11 at 17:34
@David: Yes, I understand the point now. Usually I do post some code or describe attempts, but with this implementation, I was in a hive. But I will keep the advice for later posts :) — Shamim Hafiz - MSFT, Jun 23 '11 at 06:43

Manish Singh · Answer 1 · 2020-04-20T06:58:44.773

98

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.

edited Apr 20 '20 at 06:58

answered Aug 23 '16 at 11:38

Manish Singh

5,848
4
43
31

11

It would be better to replace the expression: (l + h) / 2 with l + (h - l) / 2 to prevent a potential overflow. – Shivam Dixit Dec 10 '17 at 13:15
5

@ShivamDixit Considering 32 bit integer, you would need more than 2^30, i.e. 1073741824 elements in the array to come close to that overflow. Consider 4 byte integer array, it would take more than 4 GB or RAM to store the array. Keeping the solution simple here. This is sufficient for all online competitive programming questions. – Manish Singh Apr 29 '18 at 06:57
1

For bs_upper_bound, what if array is [1] and x=1 ? – Aroonalok Jul 06 '19 at 15:28

C. K. Young · Accepted Answer · 2011-06-22T17:04:40.660

18

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. :-)

edited Jun 22 '11 at 17:04

answered Jun 22 '11 at 16:55

C. K. Young

219,335
46
382
435

10

Although beware that `upper_bound` is *also* exactly like doing a "usual" binary search, except that if the element isn't found, you return your current place in the search. There's still a subtle difference :-). Also in both cases if the element is found you can't just stop, you have to keep checking. Basically `lower_bound` is a binary search looking for the specified "gap", the one with a lesser element on the left and a not-lesser element on the right. Then you return an iterator to the element on the right of that gap. Regular binary search is looking for an element, not a "gap", – Steve Jessop Jun 22 '11 at 16:58
Not really, if you have duplicate elements, then BSearch may end up finding a middle instance, wont it? – Shamim Hafiz - MSFT Jun 22 '11 at 17:01
@Steve: +1 That is true, and relevant if there are non-unique elements. – C. K. Young Jun 22 '11 at 17:02
1

@Gunner: See Steve's comment. I'll amend my post to make that clarification. – C. K. Young Jun 22 '11 at 17:03
1

@Steve Jessop: a rule that helps remembering where `lower_bound` and `upper_bound` point after search is that `equal_range` returns `lower_bound`..`upper_bound` range and it does exactly what it is called. – Gene Bushuyev Jun 22 '11 at 17:05
5

Note that the search leftward has to be a binary search, not a linear search. Otherwise you can violate a performance constraint. – David Thornley Jun 22 '11 at 17:13
3

And in practice you don't implement it that way, "first find a match, then find the non-match". You do what the code on cplusplus.com does, which is to search for the discontinuity you're looking for, between lesser elements and not-lesser elements. Then in `upper_bound` you search for the discontinuity between not-greater elements and greater elements. A "usual" binary search can be written more than one way - one of them ends up at the lower bound if the element is missing, another ends up at the upper bound. It depends which side of the comparison you put the sought-for element, I think. – Steve Jessop Jun 22 '11 at 17:17
Hang on, that's not right -- if the element is missing then of course the upper and lower bounds are the same! I mean if the element is *present*, but you don't return immediately when you find it. – Steve Jessop Jun 23 '11 at 11:20
1

It doesn't work this way. Your algorithm is O(n) in the worst case instead of O(log(n)) – Manish Singh Aug 23 '16 at 11:27

score 2 · Answer 3 · edited Mar 08 '17 at 10:29

I know that this is a very old post. However, I was working on a problem and I came across this post. I would like to add my iterative version for the problem which is an extension of the last answer. I checked this with the test cases I could think of. I've attached my code in C#.

This code was working for all ranges. However, the range should be within the first index to the last index+1. If the array is of size N and considering range as [0,N] the search space will be within [0,N). I know that's pretty obvious but it helped me checking some edge cases.

        static int lower_bound(int[] a, int lo,int hi, int x)
        {
            while (lo < hi) 
            {
                int mid = lo + (hi-lo) / 2;
                if(a[mid]==x)
                {
                    /*when there is a match, we should keep on searching
                    for the next same element. If the same element is not                                                         
                    found, mid is considered as the answer and added to 'hi'
                    Finally 'hi' is returned*/
                    if(a[mid-1]!=x)
                    {
                        hi=mid;
                        break;
                    }
                    else
                        hi=mid-1; 
                }
                else if(a[mid]>x)
                    hi=mid-1;
                else
                    lo=mid+1;
            }
            //if element is not found, -1 will be returned   
            if(a[hi]!=x)
                return -1;
            return hi;
        }
        static int upper_bound(int[] a, int lo,int hi, int x)
        {
            int temp=hi;
            while (lo < hi) 
            {
                int mid = lo + (hi-lo) / 2;
                if(a[mid]==x)
                {
                    /*this section make sure that program runs within        
                    range [start,end)*/
                    if(mid+1==hi)
                    {   
                        lo=mid;
                        break;
                    }
                    /*when there is a match, we should keep on searching
                      for the next same element. If the same element is not                                                         
                      found, mid is considered as the answer and added to
                      'lo'. Finally 'lo' is returned*/ 
                    if(a[mid+1]!=x)
                    {
                        lo=mid;
                        break;
                    }
                    else
                        lo=mid+1;
                }


         else if(a[mid]>x)
             hi=mid-1;
         else
             lo=mid+1;
    }
    //if element is not found, -1 will be returned
    if(a[lo]!=x)
            return -1;
        return lo;
    }

Here is a test case that I used:

Array(a) : 1 2 2 2 2 5 5 5 5
size of the array(a) : 9

Considering search element as 2:

upper_bound(a,0,9,2)=4, lower_bound(a,0,9,2)=1

Considering search element as 5:

upper_bound(a,0,9,2)=8, lower_bound(a,0,9,2)=5

Considering search element as 1:

upper_bound(a,0,9,2)=0, lower_bound(a,0,9,2)=0

Considering search element as 5:

upper_bound(a,5,9,2)=8, lower_bound(a,5,9,2)=5

score 1 · Answer 4 · answered Jul 03 '15 at 03:44

The lower_bound and upper_bound functions in python would be implemented as follows:

def binLowerBound(a, lo, hi, x):
  if (lo > hi):
    return hi
  mid = (lo + hi) / 2;
  if (a[mid] == x):
    return binLowerBound(a, lo, mid-1, x)
  elif (a[mid] > x):
    return binLowerBound(a, lo, mid-1, x)
  else:
    return binLowerBound(a, mid+1, hi, x)

def binHigherBound(a, lo, hi, x):
  if (lo > hi):
    return lo
  mid = (lo + hi) / 2;
  if (a[mid] == x):
    return binHigherBound(a, mid+1, hi, x)
  elif (a[mid] > x):
    return binHigherBound(a, lo, mid-1, x)
  else:
    return binHigherBound(a, mid+1, hi, x)

sam · Answer 5 · 2019-01-06T01:36:25.027

0

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.

edited Jan 06 '19 at 01:36

answered Nov 18 '18 at 02:21

sam

57
10

This implementation returns incorrect result if `target` is larger than the last element of `array`: it returns `size() - 1`, whereas `std::lower_bound` effectively returns `size()`. – Evg Dec 18 '18 at 11:48
@Evg Thanks for the reporting. I have fixed the bug. – sam Jan 06 '19 at 01:36

score -1 · Answer 6 · answered Jul 18 '15 at 06:06

-1

int lowerBound (int *a, int size, int val) {
   int lo = 0, hi = size - 1;
   while (lo < hi) {
      int mid = lo + (hi - lo)/2;
      if (a[mid] < val)
         lo = mid + 1;
      else
         hi = mid;
   }
   return lo;
}

answered Jul 18 '15 at 06:06

mszlazak

59
1
6

This implementation returns incorrect result if `val` is larger than the last element of `a`: it returns `size - 1`, whereas `std::lower_bound` effectively returns `size`. – Evg Dec 18 '18 at 11:52

score -1 · Answer 7 · answered Jun 19 '19 at 18:47

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

score -2 · Answer 8 · answered Mar 18 '20 at 15:43

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

Implementation of C lower_bound

8 Answers8

Linked