`binary_search<>`: On Sorted Sequence¶

More Intelligent Search ¶

When things are sorted, they give a better search

Sorted std::vector
⟶ more efficient search
⟶ binary search

int int_array[] = { 34, 45, 1, 3, 2, 666 };
std::sort(int_array, int_array+6);
bool found = std::binary_search(int_array, int_array+6, 3);

Problem

One can only decide whether the element is contained
Searching for data? ⟶ See lower_bound<>: On Sorted Sequence

Live Hacking ¶

code/binary_search.cpp¶

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>


int main()
{
    std::vector<int> array = { 34, 45, 1, 3, 2, 666 };

    // binary search requires the array to be sorted
    std::sort(array.begin(), array.end());

    // now we are prepared to search binarily
    bool is_element = std::binary_search(array.begin(), array.end(), 666);
    cout << "666 is an element: " << is_element << endl;

    return 0;
}