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

Пусть [math]t[/math] - отсортированный массив чисел из [math]n[/math] чисел. Тогда можно построить отсортированный массив [math]a: a_i \in[0, 1] \forall i = \bar{1, n}[/math]

Время работы алгоритма: [math]O(\log \log n)[/math].