Блог для любопытных и не только
Поиск

Бинарный поиск

  • Название: Binary search;
  • Применение: Поиск значения в отсортированных данных;
  • Время выполнения: О (Lon n);
  • Сложность: Легкий;
  • Входные параметры: Отсортированные данные, поисковое значение;
  • Результат: Найденное значение из n-отсортированных значений

Пример из жизни:

Допустим вы ищите в справочнике имя абонента, начинающегося с бувы «С». Как можно решить такую простую задачу? Конечно вариантов много, кто-то будет перебирать весь справочник, листая от буквы «А» потом найдет «Б» далее «В» и т.д. Но есть риск пропустить букву, например, перелистать (ведь в каждом разделе разное кол-во контактов). Можно посмотреть в оглавлении, если конечно оно есть. Наконец, если мы знеам точный порядок букв в алфавите, можно прикинуть середину справочника и открыть на половине, встретив букву «Н», зная, что «C» находится ближе к концу алфавита и повторить операцию снова.

Но что произойдет, если мы на очередном делении справочника пополам встретим букву «Ю»? Получается буква «С» осталась позади? Теперь прийдется сделать важное уточнение — после очередного деления справочника пополам, необходимо делать закладки и мысленно представить левую и правую (начало и конец половины справочника) половину т.е. запоминать предыдущее действие. Таким образом, если мы встрели букву «Ю» необходимо выбрать левую половину справочника (т.к. «C» находится в левой половине, а не правой), но никак не правую. Например, после очередного деления — получается буква «Н», поэтому необходимо указать правую половину и т.д. Наконец, при соблюдении вышеизложенной логики, после очередного действия, когда количество страниц уменьшится до одной или раньше — получаем букву «C».

Не совсем понятно? Давайте закрепим, только заместо алфавита будем искать страницу, например 285, в большой книге.

Наверное не очень понятно ? С этим можно согласиться, потому что не каждый помнит алфавит даже родного для него языка и уж точно, не каждый человек будет использоват такой хитроумный прием поиска. Все верно! Данный алгоритм, как и большинство других крайне редко используется в быту, если не используется совсем. Другое дело ЭВМ )))

Лингвистическое описание алгоритма:

Шаг 1.  Делим пополам область поиска. При этом получается два подмножества и значение на перечении этих множеств (если число элементов нечетное за пересечение множество можно взять самое большое значение из «левого» множества или самое меньшее из «правого»). Обозначим первое подмножество — «левое», второе — «правое».

Шаг 2. Если искомое значение больше, чем самое большое значение из «левого» подмножества, то исключаем из поиска все «левое» подмножество и принимаем за новую область поиска «правое подмножество» и переходим к шагу 1.

Шаг 3.  Если искомое значение меньше, чем самое большое значение из «левого» подмножества, то исключаем из поиска все «правое» подмножество и принимаем за новую область поиска «левое подмножество» и переходим к шагу 1.

Шаг 4.  Если полученное значение равно поисковому значению, то прерываем алгоритм и возвращаем полученное значение.

Блок-схема:

Программная реализация алгоритма:

Итак, основная идея бинарного поиска — деление области поиска пополам и исключение той подобласти поиска, в которой искать значение не имеет смысл. По-моему, это напоминает задачу поиска льва в пустыне, когда охотник мысленно делит площать пустыни пополам, и выбирает ту часть, где находится лев и так пока лев не окажется в зоне доступности охотника.

Итак, давайте попробуем реализовать алгоритм на одном из языке программирования. Мне нравится PHP, но думаю перенести код можно будет просто на любой другой си-подобный язык. Напишем функцию, которая на входе принимает массив из натуральныйх числе (напомню — это числа, которые используются при счете предметов)  и значение, которое необходимо найти в этом массиве.

Давайте вначале схематически изобразим массив из восьми элементов и произведем манипуляции описанные в данном алгоритме. Дан массив из 8 элементом, в котором будем искать элемент, который равен 19. На первом шаге, исходя из алгоритма, делим массив пополам. У нас получились две части. Все что слева от разделительной черты левая подобласть, остальная правая.

После деления пополам необходимо понять какую часть массива отбрасывать правую или левую. Для этого сравниваем четвертый элемент массива, который находится на границе двух частей (правой и левой). Как видно 9 меньше 19 поэтому мы смело можем отбросить левую половину массива.

Далее повторяем операцию снова, сузив область поиска. Теперь нас интересует правая часть массива с 11 элемента по 20. Опять делим пополам — получам значение 18.Данный элемент опять получился больше 19. Отбрасываем левую часть , как на прошлой итерации.

Теперь у нас осталось два элемента. При делении пополам у нас получилось значение 19. Оно равно искомому значению, поэтому необходимо отбросить правую часть массива или оставшийся элемент.

Итак, за три шага мы нашли наше значение. Если бы использовали простой перебор элементом нам понадобилось бы 6 шагов в два раза больше. А представьте массив элементов из 1 000 000 000? Преимущества очевидны.

Теперь попробуем реализовать данный алгоритм в коде:

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

Теперь необходимо обозначить границы поиска, которые будут совпадать с первым элементом массива и последним на первом шаге алгоритма.

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

Вначале делим пополам область поиска и инциализируем «серединное» значение

Проверяем значение переменной, если после деления пополам — значение посередине больше поискового значения, то смещаем границу поиска, присваяивая конечное значение этой переменной

Проверяем значение переменной, если после деления пополам — значение посередине больше поискового значения, то смещаем границу поиска, присваяивая конечное значение этой переменной

Проверяем значение переменной, если после деления пополам — значение посередине больше поискового значения, то смещаем границу поиска, присваяивая конечное значение этой переменной

Проверяем значение переменной, если после деления пополам — значение посередине больше поискового значения, то смещаем границу поиска, присваяивая конечное значение этой переменной

Поделиться