C lower_bound的实现

  • Z时代
  • 2024-01-10
  • 分类：问答

根据此处找到的以下定义

返回一个迭代器，该迭代器指向不小于value的排序范围[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);
}

回答：

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

  1. 如果找不到该元素，则返回搜索中的当前位置，而不是返回一些空值。

  2. 如果找到该元素，则向左搜索，直到找到不匹配的元素。然后，将指针/迭代器返回到第一个匹配的元素。

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

以上是 C lower_bound的实现 的全部内容， 来源链接： utcz.com/qa/415155.html

回到顶部