Interpolation Sort

Имея отсортированный массив нам надо написать функцию поиска элемента. Линейный поиск сделает это за время O(n) , Jump Search - O(√ n), а бинарный за O(log n).

Поиск с интерполяцией (Interpolation Sort) является улучшением по сравнением с бинарным поиском для экземпляров, где значения в отсортированном массиве равномерно распределены.

Двоичный поиск всегда переходит к центру. Interpolation Sort может идти в разные места в соответствии с значением ключа, по которому выполняется поиск. Например, если значение ближе к последнему элементу, поиск выгоднее начать с конца.

Сложность выйдет O(log(log n)). О том как выбрать значения ключа, поговорим в следующем посте.

Data Science: Алгоритмы и Структуры данных | Чат 💬