C语言 Clower_bound的实现

Implementation of C lower_bound

提问by Shamim Hafiz

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.

返回指向排序范围 [first,last) 中第一个元素的迭代器，该元素不比较小于 value。第一个版本使用 operator< 或第二个版本使用 comp 完成比较。

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.

lower_bound() 的 C 等效实现是什么？我知道这将是对二分搜索的修改，但似乎不能完全确定确切的实现。

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

}

采纳答案by Chris Jester-Young

lower_boundis almost like doing a usual binary search, except:

lower_bound几乎就像做一个通常的二分搜索，除了：

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.

1. 如果未找到该元素，则返回搜索中的当前位置，而不是返回一些空值。
2. 如果找到该元素，则向左搜索，直到找到不匹配的元素。然后返回指向第一个匹配元素的指针/迭代器。

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

是的，就是这么简单。:-)

回答by manish_s

Here are the equivalent implementations of upper_boundand 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.

以下是相当于实现upper_bound和lower_bound。该算法在最坏情况下为 O(log(n))，与在最坏情况下达到 O(n) 的公认答案不同。

Note that here highindex is set to ninstead 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.

请注意，这里的highindex 设置为n而不是n - 1。这些函数可以返回一个超出数组边界的索引。即，如果未找到搜索键并且它大于所有数组元素，它将返回数组的大小。

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.

实际的 C++ 实现适用于所有容器。你可以在这里找到它。

回答by Pirooz

The lower_boundand upper_boundfunctions in python would be implemented as follows:

python 中的lower_bound和upper_bound函数将按如下方式实现：

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)

回答by kots_14

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#.

我知道这是一个很老的帖子。但是，我正在解决一个问题，我遇到了这篇文章。我想为这个问题添加我的迭代版本，这是最后一个答案的扩展。我用我能想到的测试用例检查了这一点。我已经在 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.

此代码适用于所有范围。但是，范围应该在第一个索引到最后一个索引+1 内。如果数组的大小为 N 并且将范围视为 [0,N]，则搜索空间将在 [0,N) 内。我知道这很明显，但它帮助我检查了一些边缘情况。

        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:

将搜索元素视为 2：

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

Considering search element as 5:

将搜索元素视为 5：

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

Considering search element as 1:

将搜索元素视为 1：

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

Considering search element as 5:

将搜索元素视为 5：

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

回答by sam

C++ Implementation

C++ 实现

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.

编辑：修复了不存在值的错误。

回答by am2505

Example if this is the given array

如果这是给定数组的示例

1 2 3 3 4

1 2 3 3 4

and different values of x is

和不同的 x 值是

3 then firstOccurance will be 2 and lastOccurance will be 3

3 那么 firstOccurance 将是 2 并且 lastOccurance 将是 3

2 then firstOccurance will be 1 and lastOccurance will be 1

2 那么 firstOccurance 将是 1 并且 lastOccurance 将是 1

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

10 那么 firstOccurance 将是 -1 并且 lastOccurance 将是 -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;
}

回答by user3919706

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:

我知道这是一篇很老的帖子，已经有很多答案，但我也遇到了这个问题，需要一个通用的解决方案，所以我使用 manish_s 答案来调整 gnu stdlib bsearch 函数。如果有人需要它：

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

回答by mszlazak

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