Как применить бинарный поиск для поиска точек / пар в c ++? - PullRequest
Новая
       28

Как применить бинарный поиск для поиска точек / пар в c ++?

0 голосов
/ 09 апреля 2020

Я хочу найти, существует ли пара в векторе пар, используя бинарный поиск. Вот мой код: этот код ищет только первое значение в паре:

Не могли бы вы изменить этот код, чтобы он искал точную пару? 

#include <bits/stdc++.h> 
using namespace std; 

struct compare { 
    bool operator()(const pair<int, int>& value,  
                                const int& key) 
    { 
        return (value.first < key); 
    } 
    bool operator()(const int& key,  
                    const pair<int, int>& value) 
    { 
        return (key < value.first); 
    } 
}; 

int main() 
{ 
    vector<pair<int, int> > vect; 
    vect.push_back(make_pair(1, 20)); 
    vect.push_back(make_pair(3, 42)); 
    vect.push_back(make_pair(4, 36)); 
    vect.push_back(make_pair(2, 80)); 
    vect.push_back(make_pair(7, 50)); 
    vect.push_back(make_pair(9, 20)); 
    vect.push_back(make_pair(3, 29)); 

    sort(vect.begin(), vect.end()); 

    // printing the sorted vector 
    cout << "KEY" << '\t' << "ELEMENT" << endl; 
    for (pair<int, int>& x : vect) 
        cout << x.first << '\t' << x.second << endl; 

    // searching for the key element 3 
    cout << "search for key 3 in vector" << endl; 
    if (binary_search(vect.begin(), vect.end(), 
                                  3, compare())) 
        cout << "Element found"; 
    else
        cout << "Element not found"; 

    return 0; 
}

1 Ответ

1 голос
/ 09 апреля 2020

Если вы хотите найти точную пару, вам нужно указать пару binary_search, например, 

if (std::binary_search(vect.begin(), vect.end(), std::pair{3, 42}))
 // ... found

Обратите внимание, что здесь вам не нужна пользовательская функция compare. Компаратор по умолчанию делает правильные вещи. (Фактически, вы должны использовать тот же компаратор, что и для sort элементов, в противном случае binary_search будет разбит).

Обратите внимание, что до c ++ 17, вам необходимо предоставить аргументы шаблона для pair, например, 

if (std::binary_search(vect.begin(), vect.end(), std::pair<int,int>{3, 42}))
 // ... found

Если вы хотите найти позицию найденного элемента, вы можете использовать lower_bound например, 

auto lb = std::lower_bound(vect.begin(), vect.end(), std::pair<int,int>{3, 42});  

if (lb != vect.end())    
  std::cout << "Element found at position " 
            << std::distance(vect.begin(), lb);

Также, пожалуйста, не используйте #include <bits/stdc++.h> или using namespace std;

...