Обсуждение:Интерполяционный поиск

☐ В разделе про время работы какой-то бред написан. Улучшить и дополнить, впилить замечания из Кнута, в т.ч. и про то, что можно использовать интерполяцию на ранних стадиях поиска. Написать, почему время работы — [math]log(log(n))[/math], если количество элементов уменьшается на каждом шаге с [math]n_i[/math] до [math]sqrt{n_i}[/math]. ☐ Впилить адекватную картинку.