如何从C ++中成对的排序向量中获得与给定值有关的对应对

Question

我需要从配对容器的排序向量中获取与给定值有关的对应对。使用“二进制搜索”。该怎么做？

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    vector<pair<int,int>> values;
    values.push_back(make_pair(6,9));
    values.push_back(make_pair(2,5));
    values.push_back(make_pair(12,15));

    sort(values.begin(), values.end()); // sorting the vector according to 'first' value

    /*then the vector be like [(2,5), (6,9), (12,15)]*/
    /*assume : no duplicate or overlapped pairs*/

    /* I need to implement a function to get the corresponding pair related to a given value using 'binary search' method*/
    /*eg:
      if given_value = 7, then function should be return (6,7)
      if given_value = 10, then function shold be return NULL
      how i do this. is there a predefined way to do this ? */
}

Answer 1

与自定义比较器一起使用std::lower_bound：

std::lower_bound

注意：这要求C ++ 17为可选。如果在调用者处发现了一些可以做的比较，也可以只返回迭代器（请参见上面代码中的替代方法）。