Почему алгоритм Randomized_Select таким образом?

Question

Я изучаю учебник "Введение в алгоритмы" 2-е издание. В главе 9 (Медианы и статистика порядка) я не могу понять, зачем нам нужен этот дополнительный k в алгоритме Randomize_Select. Рассмотрим этот псевдокод алгоритма в книге.

RANDOMIZED-SELECT(A, p, r, i)
1   if p = r
2       then return A[p]
3   q ← RANDOMIZED-PARTITION(A, p, r)
4   k ← q - p + 1
5   if i = k    ▹ the pivot value is the answer
6       then return A[q]
7   elseif i < k
8       then return RANDOMIZED-SELECT(A, p, q - 1, i)
9   else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

Мой вопрос: зачем нам к? Я реализовал алгоритм таким образом, и он работает (для всех примеров, на которых я тестировал алгоритм).

RANDOMIZED-SELECT(A, p, r, i)
1   if p = r
2       then return A[p]
3   q ← RANDOMIZED-PARTITION(A, p, r)
4   if i = q    ▹ the pivot value is the answer
5       then return A[q]
6   elseif i < q
7       then return RANDOMIZED-SELECT(A, p, q - 1, i)
8   else return RANDOMIZED-SELECT(A, q + 1, r, i)

Поскольку q, возвращаемая из процедуры разбиения, является индексом, который содержит элемент из набора, который он должен содержать после сортировки, если этот индекс является тем, что мы ищем, мы просто возвращаем его, если нет, мы повторяем то же самое для части который содержит элемент. Зачем нужна к? Почему алгоритм заботится о порядке элемента в каждом подмножестве? Почему бы нам не заботиться об индексе вместо этого? Работает ли моя смена во всех случаях?

Answer 1

Возвращается к определению i в RANDOMIZED-SELECT.i находится в диапазоне передаваемого массива функции, которая запускается с p до r массива A.Следовательно, выбранное значение q должно быть вычислено из указанного первого массива A.Следовательно, мы должны вычислить k (местоположение в переданном массиве), относящееся к начальному индексу, который равен p.

Более того, поскольку индекс основан на 1, здесь k долженbe q - p + 1.

Например, предположим, что A - это массив размером 10, а p = 5, r = 8.Следовательно, i изменяется с 1 на 3.Следовательно, мы должны отобразить q, который находится между 5 и 8, должны быть масштабированы от 1 до 3;поэтому k имеет ту же шкалу, что и i, что q не имеет!