一个长度为n的数组A,它是循环排序的,也就是说它的最小元素未必在数组的开头,而是在下标i,于是就有A[i]<A[i+1]…....<A[0]<A[1]…<A[i-1],例如下面的数组就是循环排序的:
378, 478, 550, 631, 103, 203, 220, 234, 279, 368, 370, 374
给定一个排序数组...,假定数组所有元素都不相同,请你给出一个复杂度为O(lgn)的算法,查找出第k小的元素。...解答这道题的关键是要找到数组中的最小值,由于最小值不一定在开头,如果它在数组中间的话,那么它一定具备这样的性质,假设第i个元素是最小值,那么有A[i-1]>A[i]<A[i+1]。...从运行结果来看,我们代码对算法的实现是正确的。