假设数组中没有重复的元素，则此算法有效。

预处理

找到中值元素，然后在该元素上旋转数组。然后继续对数组的较小部分应用此过程，直到找到单个元素为止。

在每个步骤A（m），A（m-1），....，A（0）中将数组的大半部分称为m。A（0）的大小始终为1，并且每个连续数组的大小都是前一个数组的两倍或加一。即len（A（0））=
1，len（A（n））= len（A（n-1））或len（A（n-1））+ 1。注意2 ^ n <= len（A（n））<2 ^（n + 1）。

查找长度为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，并且S（n + 1）> k。您可以在O（log k）时间内完成此操作。

然后，找到A（n）中最大的kS（n）个元素。可以使用quickselect算法（的确定性变体）在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个最大元素）。我们使用quickselect做到这一点。