Бинарный поиск производится в упорядоченном массиве.
При бинарном поиске искомый ключ сравнивается с ключом среднего элемента в массиве. Если они равны, то поиск успешен. В противном случае поиск осуществляется аналогично в левой или правой частях массива.
Алгоритм может быть определен в рекурсивной и нерекурсивной формах.
Бинарный поиск также называют поиском методом деления отрезка пополам или дихотомии .
Количество шагов поиска определится как
где n-количество элементов,
↑ — округление в большую сторону до ближайшего целого числа.
На каждом шаге осуществляется поиск середины отрезка по формуле
Если искомый элемент равен элементу с индексом mid, поиск завершается.
В случае если искомый элемент меньше элемента с индексом mid, на место mid перемещается правая граница рассматриваемого отрезка, в противном случае — левая граница. 
-
Подготовка . Перед началом поиска устанавливаем левую и правую границы массива:
left = 0, right = 19
Шаг 1 . Ищем индекс середины массива (округляем в меньшую сторону):
Сравниваем значение по этому индексу с искомым:
69
Шаг 2 . Ищем индекс середины массива (округляем в меньшую сторону):
Сравниваем значение по этому индексу с искомым:
84 > 82
Сдвигаем правую границу:
right = m >
Шаг 3 . Ищем индекс середины массива (округляем в меньшую сторону):
Сравниваем значение по этому индексу с искомым:
78
Шаг 4 . Ищем индекс середины массива (округляем в меньшую сторону):
Сравниваем значение по этому индексу с искомым:
80
Шаг 5 . Ищем индекс середины массива (округляем в меньшую сторону):
Сравниваем значение по этому индексу с искомым:
82 = 82
Решение найдено!
Чтобы уменьшить количество шагов поиска можно сразу смещать границы поиска на элемент, следующий за серединой отрезка:
left = mid + 1
right = mid — 1
Бинарный поиск — классический алгоритм. На вход алгоритм принимает отсортированный массив чисел и число для поиска. На выходе — индекс этого числа в массиве.
Алгоритмически это выглядит так:
- Запоминаем левую L и правую R границы массива (индексы, а не значения)
- Берем индекс M посередине между L и R
- Если значение массива по индексу M меньше нужного — L меняем на M, если больше — R меняем на M
- Возвращаемся на шаг 2
Таким образом мы на каждом шаге алгоритма сужаем область поиска в 2 раза. Этот алгоритм имеет сложность O(log(n)).
В теории все просто, но на практике возникают проблемы.
Приведу сразу свою реализацию, а потом разберем все проблемы.
Распространенная ошибка реализации — переполнение типа при вычислении середины интервала. Именно поэтому середина вычисляется так
Еще одна проблема — выход из алгоритма. Нужно правильно обрабатывать ситуацию, когда интервал поиска свелся к двум соседним индексам. Я для наглядности вместо хитрых операций с индексами вынес эту ситуацию в отдельный блок кода
Так же можно добавить дополнительную оптимизацию для ситуации, когда value заведомо слишком маленькое или большое. Будут такие проверки в начале метода:
Сегодня мы и изучим его. Также попытаемся ответить на такие вопросы: как бинарный поиск работает в программе, плюсы и минусы его использования у себя в коде и в каких структурах данных можно его применять, а в каких нет. Поехали!
Что такое бинарный поиск
Линейный поиск по сравнению с бинарным — дешевая подделка. Бинарный поиск — очень быстрый алгоритм с не сложной реализацией, который находит элемент с определенным значением в уже отсортированном массиве.
Очень важно помнить! Алгоритм будет работать правильно, только с отсортированным массивом. А если по случайности вы забыли отсортировать массив перед его использованием, то в большинстве случаев тот ответ, который подсчитал алгоритм, будет неверным.
Принцип работы бинарного поиска
Давайте рассмотрим задачку, чтобы понять как работает алгоритм.
Охранной службе морского флота поступило сообщение о том, что некто пытается пронести на корабль бомбу. Диверсант пока находится у причала. Допустим, что в нашем распоряжении имеется прибор, который может определить, есть ли бомба в комнате. Необходимо как можно быстрее определить, у кого находится бомба.
Самым легким и самым долгим по времени решением, будет поочередная проверка пассажиров в комнате с прибором (это линейный поиск). Но это слишком долго.
Давайте сделаем по-другому. Поделим пополам всех пассажиров и разведем их по двум комнатам. Так с помощью прибора мы сможем узнать, в какой из двух комнат находится бомба. В итоге такого маневра мы уменьшим число подозреваемых в два раза. С остальным числом подозреваемых сделаем также: разделим их на две группы и разместим в разных комнатах. Так продолжаем, пока не узнаем кто диверсант.
В задаче выше охранники использовали алгоритм двоичного поиска для нахождения диверсанта. В обычной программе принцип работы бинарного поиска такой же, как и в примере, выше.
Как создать бинарный поиск в C++
Давайте посмотрим как работает бинарный поиск на примере.В примере ниже в строке 9 мы создали массив arr на 10 элементов и в строке 12 предложили пользователю с клавиатуры заполнить его ячейки.
В строке 20 мы предлагаем пользователю ввести ключ (который нужно будет найти в массиве), а дальше мы с бинарным поиском проверим массив на наличие введенного ключа пользователем. Если мы найдем ключ в массиве, то выведем индекс ячейки, в которой находится ключ.