#Делим массив относительно рассекающего элемента <tex>x</tex>. Все элементы меньшие <tex>x</tex> будут находиться левее <tex>x</tex> в массиве и будут иметь меньший индекс и наоборот, если элементы больше <tex>x</tex>.
#Если <tex>i</tex> <tex>=</tex> <tex>k</tex>, то возвращается значение <tex>x</tex>. Иначе вызывается рекурсивно шаг 1, и выполняется поиск <tex>k</tex>-го в порядке возрастания элемента в левой части массива,если <tex>i</tex> <tex><</tex> <tex>k</tex>, или в правой части, если <tex>i</tex> <tex>></tex> <tex>k</tex>.
===Псевдокод===
select(A, l, r, k) {
if (r - l + 1 <= 5) {
sort(A[l..r]); //если элементов не больше 5, сортируем их и возвращаем к-ый элемент
return A[k];
}
for i = l..(r - 4)
sort(A[i..i + 4]; //сортируем каждую группу
i += 5;
n = r - l + 1;
j = l + 2;
Medians[1..n / 5]; //создаем массив медиан
for i = 1..n / 5
Medians[i] = A[j];
j += 5;
x = select(Medians, 1, n/5, n/10); //x - рассекающий элемент
A = share(A, l, r, x); //делим массив относительно элемента x
for i = l to r
if (A[i] == x) //находим индекс элемента x в исходном массиве
m = i;
if (m = k)
return A[m];
if (m > k)
select(A, k, r, m - k + 1); //делаем рекурсивный вызов от той части массива, где находится к-ый элемент
else
select(A, l, k, m);
}
===Примерработы алгоритма ===Рассмотрим работу алгоритма на массиве из <tex> 25 </tex> элементов, обозначенных кружками.
На вход подается массив, разобьем элементы на группы по 5 элементов.
Отсортируем элементы каждой группы и выберем медианы. Вызовемся рекурсивно от медианПолученные медианы групп отмечены белыми кружками.
[[Файл:BFPRT2поиск.png| 300px]]
Разобьем на группы по 5 медианыРекурсивно вызовемся от медиан групп и получим рассекающий элемент. На рисунке он обозначен белым кружком, внутри которого изображен символ <tex> x </tex>.Отсортируем элементы каждой группы и выберем медианы
[[Файл:BFPRTпоиск2.png| 80px300px]]
Выберем медианы медианПроведем анализ рассекающего элемента. На рисунке обозначена заштрихованная область. В эту область попали все элементы, которые точно меньше рассекающего элемента. Всего элементов во входном массиве <tex> 25 </tex>, элементов меньших рассекающего <tex> 8 </tex>. В итоге мы получили один элемент равный , что количество элементов, которые меньше опорного элемента более <tex>40\frac{3n}{10}</tex>. Это и есть рассекающий элемент.
[[Файл:поиск3.png| 300px]]
