Единообразный бинарный поиск
-
Унифицированный бинарный поиск
- Оптимизация классического алгоритма бинарного поиска
- Изобретен Дональдом Кнутом
- Приведен в книге Кнута «Искусство компьютерного программирования»
-
Особенности алгоритма
- Использует таблицу подстановки для обновления индекса массива
- Не использует среднюю точку верхней и нижней границ на каждой итерации
- Оптимизирован для архитектур, где поиск в таблице быстрее, чем сложение и сдвиг
- Подходит для множества поисковых запросов в одном массиве или нескольких массивах одинаковой длины
-
Реализация на C
- Единый алгоритм бинарного поиска реализован на C
-
Рекомендации
- Кнут, Искусство компьютерного программирования, Том 3, Страница 412, Алгоритм C
-
Внешние ссылки
- Реализация алгоритма Кнута на языке Паскаль, автор Хан де Брюйн
- Реализация алгоритма Кнута в Go, автор Адрианус Варменховен