Существует ли какое-либо исследование или теория, объединяющая бинарный поиск и интерполяционный поиск?

Я только что прочитал Можно ли считать этот алгоритм алгоритмом бинарного поиска? и вспомнил, что несколько лет назад я написал индексатор / поиск файлов журнала, чтобы найти записи журнала в больших текстовых файлах по окну даты / времени.

Делая это, я решил попробовать поиск по интерполяции (я не знал, как это называется, я сам наткнулся на эту идею). Затем по какой-то причине я продолжил идею чередования шагов интерполяции с шагами двоичного разбиения: на шаге 0 я интерполировал бы для определения контрольной точки, затем на шаге 1 я бы выбирал точную среднюю точку и т. Д.

Затем я провел сравнительный анализ системы, используя чистый интерполяционный поиск, чистый двоичный поиск и попытку комбинирования. Чередующийся подход был явным победителем, как по времени, так и по количеству тестов, необходимых для нахождения набора случайно выбранных времен.

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

Я наткнулся на известную вещь? Есть ли теоретическое обоснование того, что он быстрее для определенных типов данных? Файлы журнала обычно были большими по времени (например, 1-2 ГБ текста с, возможно, 10 миллионами строк для поиска), и распределение дат / времени в них было сложным с интенсивными всплесками активности, общим временем пиковых нагрузок и тихими временами. Мои контрольные тесты были взяты из равномерного распределения целевого времени, чтобы найти.

Я наткнулся на известную вещь?

$O(log\ log\ n)$$O(log\ n)$

• Интроспективный поиск - ваш метод (итерация между интерполяционным поиском и бинарным поиском). У меня нет более подробной информации.

• Интерполяционно-бинарный поиск (IBS) Н. Санторо, Дж. Б. Сидни (1985).

  Общая идея заключается в том, что интерполяционный поиск полезен только тогда, когда искомый массив больше заданного порога. Когда рассматриваемый сегмент поиска меньше определенного пользователем порога, двоичный поиск применяется безоговорочно. И наоборот, сверх этого порога применяется шаг интерполяционного поиска, за которым в конечном итоге следует шаг двоичного поиска.

  Это имеет много общего с вашим подходом.

• Адаптивный поиск (AS) Бьяджо Бонасера, Эмилио Феррара, Джакомо Фиумара, Франческо Пагано, Алессандро Проветти

  Используя слова авторов:

  [Интерполяционно-бинарный поиск] разработал аналогичное решение, которое объединяет (но не смешивает) вместе интерполяцию и бинарный поиск. Хотя асимптотическая сложность одинакова, есть некоторые заметные различия.

  [ПОРЕЗ]

  Следовательно, можно показать, что для любого ввода AS не будет выполнять более элементарных операций, чем IBS.

  Алгоритм может потратить до двойного числа операций по сравнению с «простым» интерполяционным поиском, тщательно выявляя лучшую половину поискового сегмента, что, в свою очередь, будет означать, что для выполнения потребуется меньше итераций (но у вас еще больше накладных расходов) ,

Чередование двух алгоритмов, чтобы получить лучшее из обоих миров, является известным приемом, хотя обычно указывается, что они запускаются параллельно и возвращают ответ, как только один из них завершается.

Хотя теоретически он быстрее, интерполяционный поиск имеет два недостатка по сравнению с бинарным поиском:

• У него ужасная (линейная) производительность в худшем случае

• Затраты на вычисление средней точки довольно велики; бинарная итерация поиска в сотни раз быстрее, чем интерполяционная

Я ожидаю, что подход, при котором вы выполняете интерполяционный поиск, когда диапазон большой, и переключаетесь на бинарный поиск, когда диапазон становится маленьким, является наиболее эффективным. Было бы хорошо, если бы вы могли попробовать этот эксперимент.

$\log n$$\log \log n$$\log n$$\log \log n$

Я думаю, что ваши результаты можно объяснить двумя явлениями:

• Сочетание с бинарным поиском позволяет избежать наихудшего поведения

• Положительный эффект перехода на бинарный поиск по небольшому набору данных