C lower_bound的实现

Question

基于此处的以下定义

返回指向排序范围[first,last]中第一个元素的迭代器,它不会比value更小.使用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);

}

Answer 1

以下是相当于实现upper_bound和lower_bound.在最坏的情况下,该算法是O(log(n)),与在最坏情况下达到O(n)的接受答案不同.

请注意,此处的high索引设置为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) / 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) / 2;
        if (x <= a[mid]) {
            h = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

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

Answer 2

lower_bound 几乎就像做一般的二分搜索,除了:

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

是的,它真的那么简单.:-)