Грокаем алгоритмы

Предположим, вы ищете фамилию человека в телефонной книге (какая древняя технология!). Она начинается с буквы «К». Конечно, можно начать с самого начала и перелистывать страницы, пока вы не доберетесь до буквы «К». Но скорее всего для ускорения поиска лучше раскрыть книгу на середине: ведь буква «К» должна находиться где-то ближе к середине телефонной книги.

Или предположим, что вы ищете слово в словаре, и оно начинается с буквы «0». И снова лучше начать с середины.

Теперь допустим, что вы вводите свои данные при входе на Facebook. При этом Facebook необходимо проверить, есть ли у вас учетная запись на сайте. Для этого ваше имя пользователя нужно найти в базе данных. Допустим, вы выбрали себе имя пользователя ~karlrnageddon~. Facebook может начать с буквы А и проверять все подряд, но разумнее будет начать с середины.

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

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

Например:

Рассмотрим пример того, как работает бинарный поиск. Сыграем в простую игру: я загадал число от 1 до 100.

Вы должны отгадать мое число, использовав как можно меньше попыток.
При каждой попытке я буду давать один из трех ответов: «мало», «много»
или «угадал».

Предположим, вы начинаете перебирать все варианты подряд: 1, 2, 3, 4... Вот как это будет выглядеть.

Это пример простого поиска (возможно, термин «тупой поиск» был бы уместнее). При каждой догадке исключается только одно число. Если я загадал число 99, то , чтобы добраться до него, потребуется 99 попыток!