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

Инвариант диапазона [lo, hi] тот же, что и в бинарном поиске (2.2.3.1) — ответ, если он есть, лежит внутри. Отличие в вычислении следующей точки проверки: вместо pos = lo + (hi-lo)/2 берётся pos = lo + (hi-lo) · (x - a[lo]) / (a[hi] - a[lo]) — линейная интерполяция, предполагающая, что значения между a[lo] и a[hi] распределены примерно равномерно, и оценивающая, на какой относительной доле пути от lo до hi должно находиться значение x. Если предположение верно, pos оказывается очень близко к истинной позиции x с первой попытки — в этом источник ускорения до O(log log n) в среднем на равномерных данных.The [lo, hi] range invariant is the same as in binary search (2.2.3.1) — the answer, if present, lies inside. The difference is in computing the next check point: instead of pos = lo + (hi-lo)/2, it's pos = lo + (hi-lo) · (x - a[lo]) / (a[hi] - a[lo]) — a linear interpolation assuming the values between a[lo] and a[hi] are roughly uniformly distributed, estimating what relative fraction of the way from lo to hi x's value should be at. If the assumption holds, pos ends up very close to x's true position on the first try — this is the source of the speedup to O(log log n) average on uniform data.

int interpolation_search(const std::vector<int>& a, int x) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi && x >= a[lo] && x <= a[hi]) {
        if (a[hi] == a[lo]) {                     // защита от деления на ноль при повторах// guard against division by zero on duplicates
            return (a[lo] == x) ? lo : -1;
        }
        int pos = lo + (int)((long long)(hi - lo) * (x - a[lo]) / (a[hi] - a[lo]));
        if (a[pos] == x) return pos;
        else if (a[pos] < x) lo = pos + 1;
        else hi = pos - 1;
    }
    return -1;
}

Переключатель распределения показывает контраст: на равномерном массиве интерполяция почти всегда быстрее бинарного поиска (счётчики сравниваются справа), на неравномерном (перекошенном) — вырождается, иногда до почти линейного числа шагов.The distribution switch shows the contrast: on a uniform array, interpolation is almost always faster than binary search (counters compared on the right); on a non-uniform (skewed) one, it degrades, sometimes to a near-linear number of steps.

Доказательство O(log log n) (Перл, 1957) опирается на предположение, что значения массива — независимые случайные величины из равномерного распределения; при этом условии интерполяция статистически "почти всегда" оценивает позицию с точностью до O(√(текущий размер диапазона)), что даёт двойной логарифм после суммирования по всем шагам. Если распределение не равномерно (степенной закон, много повторов, кластеризация), формула интерполяции может каждый раз ошибаться в одну и ту же сторону на предсказуемую величину — например, для геометрически растущей последовательности [1, 2, 4, 8, ..., 2^n] интерполяционный поиск вырождается до Θ(n), потому что вычисленная позиция почти всегда близка к hi, независимо от истинного положения x.The O(log log n) proof (Perl, 1957) relies on assuming the array's values are independent random variables from a uniform distribution; under that assumption, interpolation "almost always" estimates position to within O(√(current range size)), which yields a double logarithm after summing over all steps. If the distribution isn't uniform (a power law, many duplicates, clustering), the interpolation formula can be wrong in the same direction every time by a predictable amount — for instance, for a geometrically growing sequence [1, 2, 4, 8, ..., 2^n], interpolation search degenerates to Θ(n), because the computed position is almost always close to hi, regardless of x's true position.

Это делает interpolation search рискованным выбором без предварительного знания о распределении данных — в отличие от бинарного поиска, чья гарантия O(log n) держится вообще без предположений о значениях, только о порядке.This makes interpolation search a risky choice without prior knowledge of the data's distribution — unlike binary search, whose O(log n) guarantee holds with no assumptions about values at all, only about order.