Двоичный поиск

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

Если вы хотите ознакомиться с данным материалом в видео формате, вы можете найти запись в лектории или просто перейти по ссылке. Также вы сможете получить методичку и перезентацию на данную тему под видео - лекцией.

В одном из предыдущих конспектов я рассказывал о такой структуре данных как “Массив”. Также в предыдущем конспекте из данного цикла я рассказывал о алгоритме “Линейный поиск” в рамках структуры данных “массив”. Настоятельно рекомендую ознакомиться с данными материалами для наиболее лучшего понимания содержимого текущего конспекта

Математика

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

Представьте, что мы имеем структуру данных массив состоящий из четырех целочисленных элементов

$arr = [1, 4, 5, 8,];

Здесь мы сталкиваемся с таким термином, как множество. Множество - одно из ключевых понятий математики

Example_of_a_set.svg_320x240.png

Множество - математический объект, сам являющийся набором, совокупностью, собранием каких-либо объектов, которые называются элементами этого множества. В нашем случае переменная $arr является структурой данных массив, которая по сути является c математической точки зрения некоторым множеством. Элементы 1,4, 5 и 8. являются элементами этого множества.

Числа 1, 4, 5 и 8 в множестве $arr - это последовательность. Последовательность - это набор элементов некоторого множества.

1024px-Cauchy_sequence_illustration2_320x240.png

То есть у нас есть множество $arr, которое представляет из себя структуру данных массив, и есть некоторая последовательность в данном множестве.

Множество может быть упорядоченным, то есть элементы последовательности следуют друг за другом по определенным правилам, а может быть неупорядоченным, то есть вразброс. В нашем примере мы имеем упорядоченный массив потому что его элементы следуют друг за другом по правилу возрастания. Академически говоря мы имеем множество с упорядоченной числовой последовательностью.

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

Обращаю ваше внимание на то, что речь идет о структуре данных массив с упорядоченной числовой последовательностью.

Двоичный поиск

Приходилось ли вам играть в такую игру как “угадай число”? В этой игре первый игрок загадывает число в определенном промежутке, например от 1 до 100, а второй пытается угадать его. Игрок называет число, а загадавший сообщает: названное число больше загаданного, меньше его или оно угадано верно.

24e6ae1f2de672a51791fd2544250854_0x0w_320x240.png

Чтобы определить число за минимальное количество предположений, всегда следует начинать с пятидесяти. Если загаданное число больше названного, значит оно находится в диапазоне от 51 до 100, и следующим называется число 75, то есть середина диапазона от 51 до 100. В противном случае загаданное число находится в диапазоне от 1 до 49, и следующим называется число 25.

Каждое предположение сокращает диапазон возможных значений вдвое. Когда в диапазоне остается всего одно число, это и есть правильный ответ.

Здесь нужно сделать паузу и внимательно обратить внимание на скорость двоичного поиска. Если бы мы воспользовались линейным поиском, назвав сначала 1, затем 2, потом 3 и т.д., то для нахождения загаданного числа потребовалось бы с в среднем 50 предположений. Хочу подчеркнуть, что 50 - это среднее арифметическое, но для определения искомого числа в наборе может потребоваться и все 100 предположений, если искомый элемент находится в последней позиции заданной последовательности. При двоичном поиске каждое предположение сокращает диапазон вдвое, поэтому для получения ответа требуется намного меньше предположений.

Давайте рассмотрим таблицу где наглядно отображены все предположения для нахождения числа 33

Попытка

Предположение

Результат

Диапазон возможных значений

0

   

1-100

1

50

Меньше

1-49

2

25

Больше

26-49

3

37

Меньше

26-36

4

31

Больше

32-36

5

34

Меньше

32-33

6

32

Больше

33-33

7

33

Верно

 

Правильное число было определено всего за 7 попыток, и это максимум. Возможно, вам повезет, и вы угадаете число еще до того, как размер диапазона сократится до 1. Например, это произойдет, если загадать число 50 или 34.

Давайте рассмотрим пример реализации алгоритма двоичный поиск на языке PHP

1 <?php
2
3 $arr = [1, 4, 5, 8, 14, 58, 122, 400, 866, 918];
4
5 function binary_search(int $needle, array $haystack) {
6     $firstNum = 0;
7     $lastNum = count($haystack);
8
9
10     while (true) {
11         $pos = (int) (($firstNum + $lastNum) / 2);
12         echo "assumption: ${pos} \n";
13
14         if ($haystack[$pos] === $needle) {
15             return $pos;
16         } elseif ($firstNum > $lastNum) {
17             return count($haystack);
18         } else {
19             if ($haystack[$pos] < $needle) {
20                 $firstNum = $pos + 1;
21             } else {
22                 $lastNum = $pos - 1;
23             }
24         }
25     }
26 }
27
28 $pos = binary_search($argv[1], $arr);
29
30 echo count($arr) . " elements in set \n";
31 echo 'found needle "' . $arr[$pos] . '" in position ' . $pos . "\n";

Разбор

  • В пятой строке кода мы декларируем функцию с именем binary_search которая в качестве первого аргумента принимает искомое значение, а в качестве второго некоторое множество в виде массива
  • В шестой строке кода мы указываем первую позицию в множестве
  • В седьмой строке мы указываем последнюю позицию в множестве
  • В десятой строке кода мы объявляем бесконечный цикл, который будет прерван только в том случае, если искомый элемент будет найден или если все элементы последовательности данного множества были рассмотрены и искомый элемент не был обнаружен. Точки выхода из цикла находятся на строках 15 и 17
  • В одиннадцатой строке кода производится попытка угадать число разделяя последовательность в каждой итерации - пополам
  • Если элемент в рамках каждой итерации не был найден и элементы для перебора еще существуют, то если искомый элемент больше значения элемента расположенного в середине массива, то мы присваиваем текущую позицию взамен первой и смещаем ее на единицу в большую сторону, говоря тем самым, что следующее деление пополам будет производится в интервале от 51 - 100, в противном случае присваиваем текущую позицию взамен последней и вычитаем из нее одну единицу, говоря тем самым, что следующее деление пополам будет производится в интервале от 0 - 49.
  • В следующей итерации производится разделение нового интервала пополам и т.д., точно также как в игре “угадай число”

Давайте запустим нашу программу:

php search.php 918
assumption: 5
assumption: 8
assumption: 9
10 elements in set
found needle "918" in position 9

В рамках нашей программы мы пытаемся найти число 918. Я специально выбрал такое число, потому что оно находится в последней позиции нашего с вами массива. Программа сделала 3 предположения перед обнаружением искомого элемента. Сначала наш алгоритм предположил, что число 18 находится в 5 позиции, затем в 8 и только потом в 9. Ровно за 3 шага алгоритма загаданное число было найдено. Для сравнения алгоритму “линейный поиск” потребовалось бы 10 шагов, чтобы обнаружить искомый элемент.

Недостатки

При сравнении алгоритмов “линейный” и “двоичный” поиск наглядно видно, что в полной мере более эффективным можно считать второй

featured2_320x240.jpg

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

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

Информация

Автор конспекта


Дата создания: 04.01.2019
Категория: Алгоритмы и структуры данных