面试算法：在循环排序数组中快速查找第k小的值
一个长度为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小的元素。对于上面例子，如果k = 10，那么对应元素为478.
解答这道题的关键是要找到数组中的最小值，由于最小值不一定在开头，如果它在数组中间的话，那么它一定具备这样的性质，假设第i个元素是最小值，那么有A[i-1]>A[i]<A[i+1]。要找到最小元素，一个简单办法是遍历整个数组，然后判断当前元素是否具备前面说到到的性质，当时遍历整个数组的时间复杂度是O(n)，这就超出题目对时间复杂度的要求。
如何快速找到最小值呢？我们先取数组最后一个元素A[n-1]，先判断它是否就是最小值，如果是的话，一定有A[n-2]>A[n-1]。如果不是，那么最小值在数组中间某个位置，根据定义，最小值右边的元素都会小于等于A[n-1]，而左边的元素都会大于A[n-1]，根据这个性质，我们可以通过折半查找来获得最小值。
首先用两个指针begin 和 end分别指向数组的开头和结尾，然后去中点 m = (begin + end) / 2。如果A[m] > A[n-1]，那么我们可以确定最小值在m的右边，于是在m 和 end之间做折半查找。如果A[m] < A[n-1]，那么我们根据前面的不等式判断一下当前元素是否是最小值，如果不是，那么最小值在m的左边，于是我们在begin 和 m 之间折半查找，如此我们可以快速定位最小值点。这种查找方法使得我们能够在lg(n)时间内查找到最小值。
当找到最小值后，我们就很容易查找第k小的元素，如果k比最小值之后的元素个数小的，那么我们可以在从最小值开始的数组部分查找第k小的元素。如果k比最小值之后的元素都要大，假设从最小值开始到最后一个元素，个数是t，那么我们只要在最小值前面的数组获取第k - t小的元素就可以了，具体实现如下：
public class BinarySearchInCyclicallySortedArray {
private int[] cySortedArray = null;
private int kToFind = -1;
private int posOfSmallestElement = -1;
public BinarySearchInCyclicallySortedArray(int[] A, int k) {
this.cySortedArray = A;
this.kToFind = k;
this.findSmallestElement();
}
private void findSmallestElement() {
int n = cySortedArray.length;
//先确定最后一个元素是否是最小值
if (cySortedArray[n - 1] < cySortedArray[n-2]) {
posOfSmallestElement = n - 1;
return;
}
//折半查找最小元素
int begin = 0, end = n-1;
int m = -1;
while (begin <= end) {
m = (begin + end) / 2;
//判断元素是否就是最小元素
if (cySortedArray[m-1] > cySortedArray[m] && cySortedArray[m] < cySortedArray[m+1]) {
posOfSmallestElement = m;
return;
}
//如果大于A[n-1]表明最小元素在m和end之间
if (cySortedArray[m] > cySortedArray[n-1]) {
begin = m + 1;
}
//如果小于A[n-1]表明最小元素在begin和m之间
if (cySortedArray[m] < cySortedArray[n-1]) {
end = m - 1;
}
}
posOfSmallestElement = m;
}
public int getGivenElement() {
int n = cySortedArray.length;
if (kToFind < n - posOfSmallestElement - 1) {
return cySortedArray[posOfSmallestElement + kToFind - 1];
} else {
// 减1是因为数组下标从0开始
int k = kToFind - ( n - posOfSmallestElement) - 1;
return cySortedArray[k];
}
}
}
主入口处的函数为：
public class Searching {
public static void main(String[] args) {
int A[] = {378, 478, 550, 631, 103, 203, 220, 234, 279, 368, 370, 374};
int k = 10;
BinarySearchInCyclicallySortedArray bs = new BinarySearchInCyclicallySortedArray(A, k);
int v = bs.getGivenElement();
System.out.println("the " + k + " th element in cyclically sorted array is : " + v);
}
}
上面代码运行后结果如下：
屏幕快照 2018-07-14 下午5.49.33.png
从运行结果来看，我们代码对算法的实现是正确的。
更多技术信息，包括操作系统，编译器，面试算法，机器学习，人工智能，请关照我的公众号：
