c++ - lower_bound 执行二进制搜索

Question

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

即我的 vector 如下所示。

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

您需要像在 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; } );