面试算法：在未知长度的排序数组中进行快速查找
假设A是一个排好序的数组，但是它的长度，我们无法得知。如果我们访问的元素超出了数组长度，那么就会引发一次异常，请设计一个有效算法，输入数组A以及一个数值k，找到一个下标i，使得A[i] = k, 返回-1，如果数组A中不存在等于k的元素。
这道题跟我们以前处理的查找问题不同之处在于，数组A的长度无法确定。如果数组A长度确定的话，那么问题就退化为一个在排序数组中进行查找的问题，此时我们依靠二分查找法就能快速定位数组A是否包含给定元素。
问题在于，数组A长度无法提前确定，那么我们就不能直接使用二分查找，因为我们无法定位中点，在使用二分查找时，我们需要知道起点b,终点e,然后定位中点m = (b+e)/2, 然后看A[m]与要查找数值的关系，如果A[m]大于k，那么我们就可以在[b,e]中二分查找，如果A[m]小于k,那么我们就可以在[b,e]中二分查找。由此当e不能确定时，我们无法计算m。
在不确定长度的排序数组中进行查找时，我们可以这么做。我们依次查找A[0],A[1],A[2],A[4],…，如果A[i]比k小，那么我们就将当前访问元素的下标增加一倍，假定A[p]比k小，但是访问A[2p]时越界产生了异常，那么我们就在区间[p, 2p]间进行二分查找，当然如果在产生异常前，我们找到p,使得A[p]大于k，那么我们就可以直接在区间[0, p]间进行二分查找就可以了。我们看看相关的实现代码：
public class SearchingUnkownLengthSortedArray {
private int[] array = null;
public SearchingUnkownLengthSortedArray(int[] A) {
this.array = A;
}
private int binarySearch(int[] A, int k, int begin, int end) {
/*
* 在区间[begin, end]中进行二分查找，如果找到则返回下标，找不到则返回-1
*/
while (begin <= end) {
int m = (begin + end) / 2;
//如果访问A[m]出现异常，那么把end设置为m-1，然后继续执行二分查找
try {
if (A[m] == k) {
return m;
}
if (A[m] < k) {
begin = m + 1;
}
if (A[m] > k) {
end = m - 1;
}
}catch (ArrayIndexOutOfBoundsException e) {
System.out.println("mid point out of length: " + m);
end = m - 1;
}
}
return -1;
}
public int searchingWithUnknownLength(int k) {
/*
* 下标从0，1，2依次倍增，如果下标增加到2p时，访问越界，那么在[p, 2p]间进行二分查找
*/
if (this.array[0] == k) {
return 0;
}
if (this.array[0] > k) {
return -1;
}
int endKeeper = 1;
while (true) {
try {
if (this.array[endKeeper] < k) {
endKeeper = endKeeper << 1;
} else if (this.array[endKeeper] == k){
return endKeeper;
}else {
return this.binarySearch(this.array, k, 0, endKeeper);
}
}catch(ArrayIndexOutOfBoundsException e) {
System.out.println("index out of array length: " + endKeeper);
return this.binarySearch(this.array, k, endKeeper >> 1, endKeeper);
}
}
}
}注意到代码实现中，有两处对数组下标访问溢出进行了捕捉。一是倍增下标，探测数组结尾时会产生数组访问溢出，二是在binarySearch中进行二分查找时，由于给定的末尾很可能远远超出数组末尾，因此获取中点m时任然有可能产生数组访问溢出，在二分查找时，一旦出现溢出，我们可以确定数组末尾一定在当前计算的中点之前，因此调整二分查找的区间末尾后，再次进行查找即可，注意代码实现中，从没有考虑数组长度。
我们构造一个排序数组，然后调用上面代码查询给定元素，相关代码如下：
public class Searching {
public static void main(String[] args) {
int A[] = {1, 2, 3, 4 , 5, 6, 7, 8, 9 , 10};
SearchingUnkownLengthSortedArray su = new SearchingUnkownLengthSortedArray(A);
int idx = su.searchingWithUnknownLength(10);
if (idx != -1) {
System.out.println("The given key is at index of " + idx);
} else {
System.out.println("The array do not contain the given key");
}
}
}上面代码运行后如图：
上面代码运行的时间复杂度是lg(n)，其中n是数组的长度。
腾讯云开发者
