一个长度为n的数组A,它是循环排序的,也就是说它的最小元素未必在数组的开头,而是在下标i,于是就有A[i]循环排序的:
378, 478, 550, 631, 103, 203, 220, 234, 279, 368, 370, 374
给定一个排序数组...如果A[m] > A[n-1],那么我们可以确定最小值在m的右边,于是在m 和 end之间做折半查找。...如果A[m] 值,如果不是,那么最小值在m的左边,于是我们在begin 和 m 之间折半查找,如此我们可以快速定位最小值点。...这种查找方法使得我们能够在lg(n)时间内查找到最小值。
当找到最小值后,我们就很容易查找第k小的元素,如果k比最小值之后的元素个数小的,那么我们可以在从最小值开始的数组部分查找第k小的元素。