Функция binary_search

Функция binary_search из заголовочного файла algorithm выполняет бинарный поиск значения в отсортированном диапазоне. Она возвращает true, если элемент найден, и false в противном случае. В первый параметр передается итератор начала диапазона, во второй - итератор конца диапазона, а в третий - искомое значение. Диапазон обязательно должен быть отсортирован по возрастанию, иначе результат работы функции не определен.

Синтаксис

binary_search(first, last, value)
binary_search(first, last, value, comp)

Пример

Давайте проверим, содержится ли число 3 в отсортированном векторе:

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

int main()
{
	vector<int> vec = {1, 2, 3, 4, 5};
	bool res = binary_search(vec.begin(), vec.end(), 3);
	cout << res << endl;
	return 0;
}

Результат выполнения кода:

1

Пример

Давайте проверим, содержится ли число 6 в отсортированном векторе:

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

int main()
{
	vector<int> vec = {1, 2, 3, 4, 5};
	bool res = binary_search(vec.begin(), vec.end(), 6);
	cout << res << endl;
	return 0;
}

Результат выполнения кода:

0

Пример

Давайте проверим, содержится ли строка "bcd" в отсортированном векторе строк:

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

int main()
{
	vector<string> vec = {"a", "b", "c", "d", "e"};
	bool res = binary_search(vec.begin(), vec.end(), "bcd");
	cout << res << endl;
	return 0;
}

Результат выполнения кода:

0

Смотрите также

функция lower_bound,
которая возвращает итератор на первый элемент не меньше заданного
функция upper_bound,
которая возвращает итератор на первый элемент больше заданного
функция equal_range,
которая возвращает диапазон элементов, равных заданному
функция find,
которая ищет элемент в диапазоне