该算法在假设数组中没有重复元素的情况下工作。
预处理
找到中间元素,并以该元素为基础对数组进行旋转。然后继续对数组的较小一半应用此过程,直到只剩下一个元素。
对于某个 m,在每个步骤中调用数组的较大一半 A(m)、A(m-1)、....、A(0)。 A(0) 的大小始终为 1,并且每个连续数组的大小要么是前一个数组大小的两倍,要么加一。即,len(A(0)) = 1、len(A(n)) = len(A(n-1)) 或 len(A(n-1))+1。请注意,2^n
查找长度为 n 的数组的中值需要 O(n) 时间(使用众所周知的线性时间中值查找算法),并且旋转也需要 O(n) 时间。您正在递归地应用此方法(在较小的一侧),总共需要 n + n/2 + n/4 + ... = O(n) 时间。
查找第 k 个元素
将 S(n) 定义为 A(0)、A(1)、...、A(n-1) 的长度之和。 (S(0)= 0)。
找到 n 使得 S(n) k。您可以在 O(log k) 时间内完成此操作。
然后,找到A(n)中的k-S(n)个最大元素。这可以使用快速选择算法(的确定性变体)在 O(len(A(n))) 时间内完成。由于 len(A(n)) 是 Theta(k),因此在 O(log k) + O(k) = O(k) 时间内找到该元素。
理解注意事项
首先考虑 n 是 2 减 1 的幂的情况会更容易。然后子数组 A(i) 的大小加倍。例如,当 n 为 16,并且输入是按某种顺序排列的数字 0 到 15 时,子数组可能如下所示:
A(0) = [0]
A(1) = [2, 1]
A(2) = [6, 3, 4, 5]
A(3) = [15, 8, 11, 10, 7, 12, 13, 9, 14]
要找到第 7 大元素,我们发现它必须位于 A(2) 中,并且 A(0) 和 A(1) 中组合了 3 个元素,因此我们需要找到 A(2) 中的 7-3 = 4 大元素)。我们使用快速选择来做到这一点。