Изменения

Этот алгоритм почти ни чем не отличается от алгоритма [[Поиск k-ой порядковой статистики|поиска k-ой порядковой статистики]], но имеет важное отличие в том, что время работы алгоритма в наихудшем случае равно <tex>O(n)</tex>, что будет доказано ниже. Главная идея алгоритма заключается в том, чтобы ''гарантировать'' хорошее разбиение массива. Алгоритм выбирает такой рассекающий элемент, что количество чисел, которые меньше рассекающего элемента, не менее <tex>\frac{3n}{10}</tex>, при этом количество элементов . Элементов больших рассекающего опорного элемента , также не менее <tex>\frac{3n}{10}</tex>, где <tex>n</tex> количество элементов в массиве, благодаря . Благодаря этому алгоритм работает за линейной время в любом случае.

Проведем анализ рассекающего элемента. На рисунке обозначена заштрихованная областьобозначены закрашенные области, в левом верхнем и в правом нижнем углах. В эту область эти области попали все элементы, которые точно меньше или больше рассекающего элемента, соответственно. Всего В каждой области по <tex> 8 </tex> элементов во входном , всего же в массиве <tex> 25 </tex>, элементов меньших рассекающего то есть мы получили хорошее разбиение массива относительно опорного элемента, так как <tex> 8 > </tex>. В итоге мы получили, что количество элементов, которые меньше опорного элемента более <tex>\frac{3n3 \cdot 25}{10}</tex>.  [[Файл:поиск3Теперь докажем, что алгоритм также хорошо выбирает опорный элемент и в общем случае. Доказательство представлено ниже.png| 300px]]

# Тогда, по предположению индукции, <tex>T(\frac{n}{5}) \le 10C(\frac{n}{5}) = 2Cn</tex> и <tex> T(\frac{7n}{10}) \le 10C(\frac{7n}{10}) = 7Cn</tex>, тогда