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

Двоичный поиск обеспечивает значительное увеличение скорости поиска по сравнению с полным перебором. Он

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

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

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

При интерполяционном поиске индексы известных

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