Binary поиск считается быстрым алгоритмом поиска, подходит для наборов данных любого разумного размера. В отличие от линейного поиска, может использоваться даже для очень больших наборов данных, потому что исключает большое количество сравнений. Binary поиск отличается от линейного поиска тем, что в нем требуется, чтобы данные были обязательно сортированы.
Рассмотрим пример, как он искал бы элемент в следующем векторе.
Рисунок 1 Вектор, содержащий девять элементов
Найти элемент, который содержит значение 9. Все двоичные поиски начинаются, с исследования элемента находящегося строго по середине набора данных. В этом примере этот элемент содержит цифру 21.
Рисунок 2 Выбор среднего элемента
Значение, которое мы ищем, 9. Так как 9 меньше чем 21, мы знаем он должен быть сохранен слева от среднего элемента. Поэтому мы можем безопасно проигнорировать правую половину вектора и продолжить поиск рассматривая левую половину вектора. Рисунок 3 демонстрирует это разделение вектора.
Рисунок 2 Разделение вектора
Еще раз разделим левую часть по середине и это значение оказывается равным 5. Так как 5 меньше 9, делаем вывод 9 должна быть в правой половине этой части. Далее, снова игнорируем левую половину этого раздела, и наконец находим искомое число.
Рисунок 4 Разделение вектора, снова
Для заданного вектора, который содержит девять элементов, было сделано только три сравнения, чтобы найти искомый элемент. Начиная выполненние с левой стороны вектора, линейный поиск должен сделать только три сравнениях. Реальное преимущество двоичного поиска появляется, когда необходимо рассматривать большие наборы данных. Следующая таблица приводит максимальное количество сравнений, которые алгоритм двоичного поиска должен сделать, чтобы найти любой элемент в векторах различных размеров.
| Size of vector | Max comparisons |
| 1,000 | |
| 10,000 | |
| 100,000 | |
| 1,000,000 | |
| 10,000,000 | |
| 100,000,000 | |
| 1,000,000,000 |
Таблица 1 Максимальные сравнения двоичного поиска
Даже для вектора, который содержит миллиард элементов, алгоритм двоичного поиска должен сделать самое большее тридцать сравнений, чтобы найти любой элемент. Реализация алгоритма двоичного поиска приведена в Листинге 2.
| 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: | // Finding an element in a vector using binary search template <typename T> int binary_search(const vector<T>& v, const T& item) { int low = 0; int high = v.size() - 1; int mid; while (low <= high) { // find the midpoint mid = (low + high) / 2; if (v[mid] < item) { low = mid + 1; // look in upper portion } else if (v[mid] > item) { high = mid - 1; // look in lower portion } else { return mid; // found it! } } return -1; // item not found } |
| Listing 2Finding an element in a vector using a binary search |
Единственный недостаток двоичного поиска это то, что он требует сортированных данных. Без сортированных данных двоичный поиск бессмыслен, как и результат его поиска - не верен. Если имеется вектор несортированных элементов, то его следует сначала сортировать, чтобы затем мы могли бы использовать двоичный поиск. Сказанное нашло отражение в 4.1.2 Основные алгоритмы сортировки.
Вместо того, чтобы положиться на их собственные реализации двоичного поиска, программисты на C++ могут использовать функцию STL binary_search. Интерфейс STL binary_search напоминает интерфейс функции find. Единственной разницей является то что функция binary_search возвращает bool значение, указывающее на успешность поиска. Использование в качестве примера STL binary_search приведено в wordsearch.cpp. Программа хранит слова, содержащиеся в текстовом файле. Пользователь вводит искомое слово и программа выполняет двоичный поиск, и находит это слово. Этот текст можно скачать здесь.