std::binary search

std::binary search (tsz. std::binary searches)

1. (informatika)

A std::binary_search egy algoritmus a <algorithm> könyvtárban, amely gyorsan megmondja, hogy egy adott érték megtalálható-e egy rendezett tartományban (például vektorban vagy tömbben).

bool result = std::binary_search(begin, end, value);

• begin és end – a rendezett tartomány határai
• value – a keresett érték
• Visszatérési érték: true, ha megtalálta, false, ha nem.

• Csak rendezett adatstruktúrában működik jól!
• Belsőleg bináris keresést használ (O(log n) időbonyolultság).

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> numbers = {1, 3, 5, 7, 9, 11};
    int keresett = 7;

    if (binary_search(numbers.begin(), numbers.end(), keresett)) {
        cout << "A(z) " << keresett << " benne van a sorozatban." << endl;
    } else {
        cout << "A(z) " << keresett << " nincs benne a sorozatban." << endl;
    }
}

A(z) 7 benne van a sorozatban.

• Először ellenőrzi a középső elemet.
• Ha az kisebb a keresett értéknél, akkor a jobb oldalra megy.
• Ha nagyobb, akkor a bal oldalra megy.
• Addig felezi a keresési tartományt, amíg el nem éri a találatot vagy a végét.

• std::binary search - Szótár.net (en-hu)
• std::binary search - Sztaki (en-hu)
• std::binary search - Merriam–Webster
• std::binary search - Cambridge
• std::binary search - WordNet
• std::binary search - Яндекс (en-ru)
• std::binary search - Google (en-hu)
• std::binary search - Wikidata
• std::binary search - Wikipédia (angol)