lower_bound 进行二分查找

Question

这里我使用std::lower_bound()创建了一个二进制搜索函数。如下图。如果我传递 std::pair，这会很好地工作，但是我只想对 pair 的第一个值执行二进制搜索。我认为在 lower_bound() 的 Comp 参数中可以做到这一点，但不完全确定如何做到。

即我的向量如下所示。

std::vector<std::pair<int,double>> v;

我只想比较第一个值，即 int。

template<class ForwardIt, class T>
ForwardIt binary_searcht(ForwardIt first, ForwardIt last, const T& value)
{
    ForwardIt i = std::lower_bound(first, last, value);
    if (i != last && !(value < *i))
        return i;
    else
        return last;

}

Answer 1

使用自定义比较函数 comp 并与 std::lower_bound

一起使用

bool comp( std::pair<int , double> &x , std::pair<int , double> &y)
{
     return x.second < y.second;
}
std::lower_bound(v.begin(),v.end(),value, comp);

Answer 2

您需要将比较 class 添加到您的函数中，就像在 std::lower_bound:

中所做的那样

template<class ForwardIt, class T, class Compare>
ForwardIt binary_searcht(ForwardIt first, ForwardIt last, const T& value, Compare cmp)
{
    ForwardIt i = std::lower_bound(first, last, value, cmp);
    if (i != last && !cmp(value, *i))
        return i;
    else
        return last;

}

typedef std::pair<int,double> mypair;
std::vector<mypair> v;
auto f = binary_searcht( v.begin(), v.end(), value, 
    []( const mypair &p1, const mypair &p2 ) { return p1.first < p2.first; } );

Answer 3

std::lower_bound的第二个定义是：

template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

因此，您可以编写自己的比较对的函数并使用它。您的模板函数将如下所示：

template<class ForwardIt, class T, class Compare>
ForwardIt binary_searcht(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    ForwardIt i = std::lower_bound(first, last, value, comp);
    if (i != last && !(value < *i))
        return i;
    else
        return last;
}

而且，如果你想将它用于 std::vector< std::pair<int,double> > 的元素，你应该这样调用它：

bool compare(std::pair<int, double> a, std::pair<int, double> b) {
    return a.first < b.first;
}
binary_searcht(v.begin(), v.end(), value, compare);

或者，如果您想使用 lambda 表达式的极客 -std=c++11 方式，如果您想拥有干净的代码并且不想声明额外的函数：

typedef std::pair<int, double> tuple2;
auto result = binary_searcht(v.begin(), v.end(), 
    [](tuple2 &a, tuple2 &b) { return a.first < b.first; } );

lower_bound 进行二分查找

lower_bound to perform binary search

c++

binary-search