面试算法：在未知长度的排序数组中进行快速查找

假设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");