c++ - 如何在C++中从成对的排序 vector 中获得与给定值有关的相应对

标签 c++ algorithm binary-search

我需要从对容器的排序 vector 中获取关于给定值的对应对。使用“二进制搜索”。怎么做?

#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 ? */
}

最佳答案

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

std::optional<std::pair<int,int>> find(const std::vector<std::pair<int, int>>& vec, int searched) {
  auto it = std::lower_bound(cbegin(vec), cend(vec), std::pair<int, int>{searched, 0}, [](const auto& a, const auto& b) {return a.first < b.first;});
  if(it == cend(vec) || searched < it->first) { // nothing found, return nullopt
    return {};
    // alt: return cend(vec);
  }
  return {*it}; // return value wrapped in optional
  // alt: return it;
}

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

关于c++ - 如何在C++中从成对的排序 vector 中获得与给定值有关的相应对,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59917814/

相关文章:

java - 为什么此二进制搜索代码在 Eclipse IDE 上给出错误的输出?

c++ - 使用 pthread 唤醒多线程的最佳方法

c++ - 我可以在 Windows 中使用自己的消息循环吗?

php - 为什么不从头开始呢?

c++ - 处理递归二分搜索中的段错误

javascript - 在 2 种口味列表中进行二分搜索

c++ - 在声明后使用方法扩展类功能

c++ - 如何在 CLion 中使用 QSerialPort?

algorithm - 在 Dijkstra 算法中每次迭代将选择具有最小距离值的顶点的引理是什么?

algorithm - n 个数字的排序时间是否取决于数字的排列?