Выбор позиции для поиска в Interpolation Search

Чтобы разделить массив на две части, мы используем следующую формулу:

mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo]), где

A - наш искомый массив
X - элемент, который мы ищем
Lo - наименьший индекс массива
Hi - наивысший индекс массива
An - значение, хранящееся под индексом n в списке.

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

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