Недавно я столкнулся с проблемой программирования, связанной с поиском в массиве временных меток записи, наиболее близкой к входной метке времени. Лучший способ решить эту проблему, который я мог придумать, - это использовать вариант двоичного поиска. Метки времени - отличный вариант использования для двоичного поиска, потому что, поскольку время всегда движется вперед, есть большая вероятность, что метки времени будут записаны и сохранены в отсортированном виде.
Это заставило меня задуматься, для каких еще проблем двоичный поиск является хорошим алгоритмом?
Двоичный поиск - это алгоритм, который выполняется за время log (n) и который работает значительно лучше, чем наивный перебор каждого элемента в отсортированном массиве для поиска значения O (n).
Самый простой вариант использования двоичного поиска - это проверка того, существует ли значение в отсортированном массиве. Например, если я провожу мероприятия 1 января, 12 января, 2 февраля, 3 февраля и 15 февраля, и вы спрашиваете меня, есть ли мероприятие 3 февраля, вместо того, чтобы начинать с начала и смотреть на каждую дату, проверяя Независимо от того, было ли это 3 февраля, я бы сначала посмотрел на среднюю дату, проверил, появился ли этот элемент до или после 3 февраля, а затем повторил это либо для верхней, либо для нижней половины массива. Базовая реализация функции двоичного поиска возвращает `True`, если дата находится в массиве, в противном случае `False`.
Ради интереса я написал как итеративную, так и рекурсивную реализации базового двоичного поиска (на Python):
Другой иллюстративный вариант использования двоичного поиска - это классическая игра в угадывание. Если я выберу число от 1 до 100, сколько предположений вам потребуется, чтобы найти, какое число я выбрал? Предположим, что для каждого предположения я сообщаю вам, было ли ваше предположение слишком высоким или слишком низким. Если вы начнете с 1 и угадываете каждое число по порядку, вам может потребоваться 100 угадываний. Но если вы угадываете середину и знаете, двигаться ли каждый раз выше или ниже? Максимальное количество предположений будет всего 7.
Ниже приведен код, который возвращает количество итераций, необходимых для поиска элемента (в Python):
Хорошо, теперь мы переходим к хорошему. Есть радиостанция, которая решает подарить супер-крутой отпуск для звонящего, который звонит в 11 утра, и нам нужно выяснить, кто это был. Если у нас есть журнал всех звонков, мы можем использовать двоичный поиск, чтобы найти звонок в 11 утра, но что, если никто не позвонил ровно в 11: 00: 00: 00? Мы можем внести еще одну небольшую модификацию в наш алгоритм двоичного поиска, чтобы вернуть запись о вызывающем абоненте, который звонил ближе всего к 11 часам утра.
Вот ближайшая реализация бинарного поиска (на Python):
Эти примеры действительно помогли мне понять, как работает двоичный поиск, и где / почему / когда его использовать. Не стесняйтесь взять код и попробовать запустить или изменить его самостоятельно.
