Как получить соответствующую пару относительно заданного значения из отсортированного вектора пар в C ++ - PullRequest
Новая
       4

Как получить соответствующую пару относительно заданного значения из отсортированного вектора пар в C ++

1 голос
/ 26 января 2020

Мне нужно получить соответствующую пару относительно заданного значения из отсортированного вектора контейнера пары. используя «бинарный поиск». как это сделать? 

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

1 Ответ

3 голосов
/ 26 января 2020

Используйте 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. Вы также можете просто вернуть итератор, если вы нашли что-то и сделать сравнение в вызывающей программе (см. Альтернативы в коде выше).

...