Принцип алгоритма: на входе он получает отсортированный список элементов. Если искомый элемент находится в списке, бинарный поиск возвращает его позицию. В противном случае бинарный поиск возвращает null.
Пример: Гоша и Рита играют в игру. Гоша загадал число от 0 до 100. Рита должна его отгадать, используя при этом как можно меньше попыток. При каждой попытке Гоша даёт один из трёх ответов: «мало», «много» и «угадала».
Самый эффективный способ отгадать загаданное число — начать с середины.
Рита: 50.
Гоша: Мало.
Теперь Рита знает, что все числа от 1 до 50 не подходят. То есть за одну попытку она исключила половину чисел.
Следующая попытка:
Рита: 75.
Гоша: Много.
И Рита снова исключила половину от оставшихся чисел: 75 — 100 не подходят. Выбор сузился до 24 чисел.
Принцип бинарного поиска состоит в том, что мы каждый раз проверяем элемент в середине диапазона и исключаем половину его элементов. В общем случае для списка из n элементов бинарный поиск будет выполнен за log₂n шагов.
Python: