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

Алгоритм:

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

Пример реализации:

Дан массив возрастов невест: 1 2 5 7 12 13 18 49 56 72 106

Ключ: 18

Средний элемент с индексом 5 является число 13, которое меньше 18. Левая половина массива отбрасывается, дальше в поиске участвует только правый массив 18 49 56 72 106. Средний элемент 56 больше 18. Останется массив 18 49. Поскольку в данном массиве всего два элемента и нет среднего для порядка будем округлять в меньшую сторону. Это элемент 18. 

Сравнение эффективности алгоритмов:

Если массив будет содержать 1024 элемент бинарный поиск справится с задачей за 11 сравнений (O(log(n))) против 1024 сравнений перебором O(n).

Если массив будет содержать 1 000 000 элементов бинарный поиск справится с задачей за 21 сравнение (O(log(n))) против 1 1 000 000 сравнений перебором O(n).

Шаг 1: Из одиннадцати элементов