std::binary_search
![]() |
Эта страница была переведена автоматически с английской версии вики используя Переводчик Google.
Перевод может содержать ошибки и странные формулировки. Наведите курсор на текст, чтобы увидеть оригинал. Вы можете помочь в исправлении ошибок и улучшении перевода. Для инструкций перейдите по ссылке. Щёлкните здесь, чтобы увидеть английскую версию этой страницы |
Определён в заголовочном файле <algorithm>
|
||
template< class ForwardIt, class T > bool binary_search( ForwardIt first, ForwardIt last, const T& value ); |
(1) | |
template< class ForwardIt, class T, class Compare > bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp ); |
(2) | |
[first, last)
содержит элемент, равный value
. Первый вариант используется operator< для сравнения элементов, вторая версия использует данную функцию сравнения comp
.[first, last)
contains an element equal to value
. The first version uses operator< to compare the elements, the second version uses the given comparison function comp
.Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
Содержание |
[править] Параметры
first, last | — | диапазон элементов для изучения
Оригинал: the range of elements to examine Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда. |
value | — | Значение для сравнения элементов
Оригинал: value to compare the elements to Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда. |
comp | — | функция сравнения, возвращающая true если первый аргумент меньше второго. Сигнатура функции сравнения должна быть эквивалентна следующей: bool cmp(const Type1 &a, const Type2 &b); Сигнатура на обязана содержать const &, однако, функция не может изменять переданные объекты. |
Требования к типам | ||
-ForwardIt должен соответствовать требованиям ForwardIterator .
|
[править] Возвращаемое значение
value
найдено, false иначе.value
is found, false otherwise.Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
[править] Сложность
first
и last
first
and last
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
[править] Возможная реализация
Первый вариант |
---|
template<class ForwardIt, class T> bool binary_search(ForwardIt first, ForwardIt last, const T& value) { first = std::lower_bound(first, last, value); return (first != last && !(value < *first)); } |
Второй вариант |
template<class ForwardIt, class T, class Compare> bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp) { first = std::lower_bound(first, last, value); return (first != last && !(comp(value, *first)); } |
[править] Пример
#include <iostream> #include <algorithm> #include <vector> int main() { std::vector<int> haystack {1, 3, 4, 5, 9}; std::vector<int> needles {1, 2, 3}; for (auto needle : needles) { std::cout << "Searching for " << needle << '\n'; if (std::binary_search(haystack.begin(), haystack.end(), needle)) { std::cout << "Found " << needle << '\n'; } else { std::cout << "no dice!\n"; } } }
Вывод:
Searching for 1 Found 1 Searching for 2 no dice! Searching for 3 Found 3
[править] См. также
возвращает набор элементов для конкретного ключа Оригинал: returns range of elements matching a specific key Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда. (шаблон функции) |