28

基于此处找到的以下定义

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

什么是 lower_bound() 的 C 等效实现。我知道这将是对二分搜索的修改，但似乎无法准确指出确切的实现。

int lower_bound(int a[], int lowIndex, int upperIndex, int e);

示例案例：

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;

我尝试的代码如下：

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

}
4

8 回答 8

89

upper_bound以下是和的等效实现lower_bound。该算法在最坏情况下为 O(log(n))，不像在最坏情况下得到 O(n) 的公认答案。

请注意，此处high的 index 设置为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;
}

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

于 2016-08-23T11:38:10.357 回答
17

lower_bound几乎就像进行通常的二进制搜索一样，除了：

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

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

于 2011-06-22T16:55:23.477 回答
2

我知道这是一个非常古老的帖子。但是，我正在解决一个问题，并且遇到了这篇文章。我想为这个问题添加我的迭代版本，这是最后一个答案的扩展。我用我能想到的测试用例检查了这一点。我在 C# 中附加了我的代码。

此代码适用于所有范围。但是，范围应该在第一个索引到最后一个索引+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;
    }

这是我使用的一个测试用例：

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

将搜索元素视为 2：

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

将搜索元素视为 5：

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

将搜索元素视为 1：

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

将搜索元素视为 5：

upper_bound(a,5,9,2)=8, lower_bound(a,5,9,2)=5
于 2017-03-08T09:57:52.110 回答
1

python中的lower_boundandupper_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)
于 2015-07-03T03:44:32.950 回答
0

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

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

于 2018-11-18T02:21:16.727 回答
-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;
}
于 2015-07-18T06:06:51.827 回答
-1

如果这是给定数组的示例

1 2 3 3 4

x 的不同值是

3 然后 firstOccurance 将是 2 并且 lastOccurance 将是 3

2 然后 firstOccurance 将是 1 并且 lastOccurance 将是 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;
}
于 2019-06-19T18:47:14.473 回答
-2

我知道这是一篇非常古老的帖子，已经有很多答案，但我也遇到了这个问题，需要一个通用的解决方案，所以我使用 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;
}
于 2020-03-18T15:43:47.690 回答