Алгоритмы и структуры данных

Интерполяционный поиск

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

Алгоритм:
Шаг 1: В цикле вычислите значение «pos», используя формулу положения датчика.
Шаг 2: Если это совпадение, верните индекс элемента и выйдите.
Шаг 3: Если элемент меньше arr[pos], вычислите положение зонда левого подмассива. В противном случае вычислите то же самое в правом подмассиве.
Шаг 4: Повторяйте до тех пор, пока не будет найдено совпадение или пока подмассив не уменьшится до нуля.

Сложность: O(log(log(n)))

www.tgoop.com/the_algorithms/4578

6.2K viewsOct 19, 2023 at 09:00

Интерполяционный поиск

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

Алгоритм:
Шаг 1: В цикле вычислите значение «pos», используя формулу положения датчика.
Шаг 2: Если это совпадение, верните индекс элемента и выйдите.
Шаг 3: Если элемент меньше arr[pos], вычислите положение зонда левого подмассива. В противном случае вычислите то же самое в правом подмассиве.
Шаг 4: Повторяйте до тех пор, пока не будет найдено совпадение или пока подмассив не уменьшится до нуля.

Сложность: O(log(log(n)))

BY Алгоритмы и структуры данных