Бинарный поиск c реализация

Бинарный поиск производится в упорядоченном массиве.

При бинарном поиске искомый ключ сравнивается с ключом среднего элемента в массиве. Если они равны, то поиск успешен. В противном случае поиск осуществляется аналогично в левой или правой частях массива.

Алгоритм может быть определен в рекурсивной и нерекурсивной формах.

Бинарный поиск также называют поиском методом деления отрезка пополам или дихотомии .

Количество шагов поиска определится как

где 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

Бинарный поиск — классический алгоритм. На вход алгоритм принимает отсортированный массив чисел и число для поиска. На выходе — индекс этого числа в массиве.

Читайте также:  Ios 12 мелодия звонка

Алгоритмически это выглядит так:

  1. Запоминаем левую L и правую R границы массива (индексы, а не значения)
  2. Берем индекс M посередине между L и R
  3. Если значение массива по индексу M меньше нужного — L меняем на M, если больше — R меняем на M
  4. Возвращаемся на шаг 2

Таким образом мы на каждом шаге алгоритма сужаем область поиска в 2 раза. Этот алгоритм имеет сложность O(log(n)).

В теории все просто, но на практике возникают проблемы.

Приведу сразу свою реализацию, а потом разберем все проблемы.

Распространенная ошибка реализации — переполнение типа при вычислении середины интервала. Именно поэтому середина вычисляется так

Еще одна проблема — выход из алгоритма. Нужно правильно обрабатывать ситуацию, когда интервал поиска свелся к двум соседним индексам. Я для наглядности вместо хитрых операций с индексами вынес эту ситуацию в отдельный блок кода

Так же можно добавить дополнительную оптимизацию для ситуации, когда value заведомо слишком маленькое или большое. Будут такие проверки в начале метода:

Сегодня мы и изучим его. Также попытаемся ответить на такие вопросы: как бинарный поиск работает в программе, плюсы и минусы его использования у себя в коде и в каких структурах данных можно его применять, а в каких нет. Поехали!

Что такое бинарный поиск

Линейный поиск по сравнению с бинарным — дешевая подделка. Бинарный поиск — очень быстрый алгоритм с не сложной реализацией, который находит элемент с определенным значением в уже отсортированном массиве.

Очень важно помнить! Алгоритм будет работать правильно, только с отсортированным массивом. А если по случайности вы забыли отсортировать массив перед его использованием, то в большинстве случаев тот ответ, который подсчитал алгоритм, будет неверным.

Принцип работы бинарного поиска

Давайте рассмотрим задачку, чтобы понять как работает алгоритм.
Охранной службе морского флота поступило сообщение о том, что некто пытается пронести на корабль бомбу. Диверсант пока находится у причала. Допустим, что в нашем распоряжении имеется прибор, который может определить, есть ли бомба в комнате. Необходимо как можно быстрее определить, у кого находится бомба.

Читайте также:  Как настроить принтер xerox phaser 3100 mfp

Самым легким и самым долгим по времени решением, будет поочередная проверка пассажиров в комнате с прибором (это линейный поиск). Но это слишком долго.

Давайте сделаем по-другому. Поделим пополам всех пассажиров и разведем их по двум комнатам. Так с помощью прибора мы сможем узнать, в какой из двух комнат находится бомба. В итоге такого маневра мы уменьшим число подозреваемых в два раза. С остальным числом подозреваемых сделаем также: разделим их на две группы и разместим в разных комнатах. Так продолжаем, пока не узнаем кто диверсант.

В задаче выше охранники использовали алгоритм двоичного поиска для нахождения диверсанта. В обычной программе принцип работы бинарного поиска такой же, как и в примере, выше.

Как создать бинарный поиск в C++

Давайте посмотрим как работает бинарный поиск на примере.В примере ниже в строке 9 мы создали массив arr на 10 элементов и в строке 12 предложили пользователю с клавиатуры заполнить его ячейки.

В строке 20 мы предлагаем пользователю ввести ключ (который нужно будет найти в массиве), а дальше мы с бинарным поиском проверим массив на наличие введенного ключа пользователем. Если мы найдем ключ в массиве, то выведем индекс ячейки, в которой находится ключ.