45

是否有使用二分搜索的函数，例如根据给定谓词lower_bound返回最后一项小于或等于的项？

lower_bound定义为：

查找值大于或等于指定值的有序范围中的第一个元素的位置，其中排序标准可以由二元谓词指定。

和upper_bound：

查找值大于指定值的有序范围中的第一个元素的位置，其中排序标准可以由二元谓词指定。

具体来说，我有一个按时间排序的事件容器，并且在给定时间内，我想找到在该点之前或该点出现的最后一个项目。我可以通过上/下界、反向迭代器和使用std::greateror的某种组合来实现这一点std::greater_equal吗？

编辑：如果您在数组开始之前要求一个点，则需要对 user763305 的建议进行调整：

iterator it=upper_bound(begin(), end(), val, LessThanFunction());
if (it!=begin()) {
  it--; // not at end of array so rewind to previous item
} else {
  it=end(); // no items before this point, so return end()
}
return it;
4

5 回答 5

47

在排序容器中，小于或等于 的最后x一个元素是大于 的第一个元素之前的元素x。

因此，您可以调用std::upper_bound，并将返回的迭代器递减一次。（在递减之前，您当然必须检查它是否不是开始迭代器；如果是，则没有小于或等于的元素x。）

于 2012-04-03T08:35:03.807 回答
8

这是一个围绕 upper_bound 的包装函数，它返回容器或数组中小于或等于给定值的最大数：

template <class ForwardIterator, class T>
  ForwardIterator largest_less_than_or_equal_to ( ForwardIterator first, 
                                                  ForwardIterator last,
                                                  const T& value)
{
  ForwardIterator upperb = upper_bound(first, last, value);

  // First element is >, so none are <=
  if(upperb == first)
    return NULL;

  // All elements are <=, so return the largest.
  if(upperb == last)
    return --upperb;

  return upperb - 1;
}

要更好地解释这是做什么以及如何使用此功能，请查看：

C++ STL — 在数组或容器中查找小于或等于给定元素的最后一个数字

于 2012-09-14T20:23:41.053 回答
7

我已经测试了您的反向迭代器解决方案，它是正确的。

给定v按“<”排序

找到最后一个小于 x 的元素：

auto iter = std::upper_bound(v.rbegin(), v.rend(), x, std::greater<int>());
if(iter == v.rend())
    std::cout<<"no found";
else
    std::cout<<*iter;

查找小于等于 x 的最后一个元素：

auto iter = std::lower_bound(v.rbegin(), v.rend(), x, std::greater<int>());
if(iter == v.rend())
    std::cout<<"no found";
else
    std::cout<<*iter;

这个比iter -= 1版本好

于 2018-05-08T03:09:42.433 回答
2

std::prev：https ://en.cppreference.com/w/cpp/iterator/prev

#include <iostream>
#include <map>

int main()
{
    std::map<int, char> m{{2, 'a'}, {4, 'b'}, {6, 'c'}, {8, 'd'}, {10, 'e'}};

    int num = 3;
    auto it = m.upper_bound(num);
    auto pv = std::prev(it);

    std::cout << "upper bound of " << num << ": "
        << it->first << ", " << it->second << '\n';
    std::cout << "lower than or equal of " << num << ": "
        << pv->first << ", " << pv->second << '\n';
}

输出：

upper bound of 3: 4, b
lower than or equal than 3: 2, a
于 2020-04-28T18:27:34.993 回答
1

Python中的一个简单实现：

def bi_search(arr, target):
    """
    index of the last element which <= target
    """

    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo - 1
于 2020-12-03T16:31:57.960 回答