Пример бинарного поиска:
Предположим вы ищите слово в словаре. Это слово начинается на букву "И". Можно, конечно, начать искать с самого начала словаря, и перелистывать страницы пока вы не доберетесь до вашей буквы "И", но это не эффективный поиск. Перед нами типичная задача поиска. Как тогда решить эту задачу?
Для решения задачи применим алгоритм "Бинарный поиск".
Бинарный поиск - это алгоритм; на входе он получает отсортированный список элементов. Если элемент, который вы ищете, присутствует в списке, то бинарный поиск возвращает ту позицию, в которой он был найден. В противном случае бинарный поиск возвращает null.
Например:
Найдем число 44 в отсортированном массиве за малое количество операции.
1. Начнем поиск с середины массива, то есть с числа 21.
2.Дальше мы проверяем это число на условие: если число меньше числа,которого мы ищем, то все числа перед числом 21 слишком малы. Иначе все числа после числа 21 слишком велики. В нашем случае, все числа до 21 малы, поэтому число 21 становится началом нашего массива.
3. Начинаем все тоже самое, что на строке номер 1.
Результатом нашего алгоритма мы найдем число 44 за 4 операции, вместо 13.
В общем случае для списка из п элементов бинарный поиск выполняется за log 2( n ) шагов, тогда как простой поиск будет выполнен за n шагов.
-------------------------------------------------------------------------------------------------
ПРИМЕЧАНИЕ
Бинарный поиск работает только в том случае, если список отсортирован. Например, имена в телефонной книге хранятся в алфавитном порядке, и вы можете воспользоваться бинарным поиском. А что произойдет, если имена не будут отсортированы?
-------------------------------------------------------------------------------------------------
Посмотрим, как написать реализацию бинарного поиска на Python.
