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

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

上面代码运行后如图：

屏幕快照 2018-07-02 下午5.55.54.png

上面代码运行的时间复杂度是lg(n)，其中n是数组的长度。

更详细的讲解和代码调试演示过程，请点击链接

更多技术信息，包括操作系统，编译器，面试算法，机器学习，人工智能，请关照我的公众号：

这里写图片描述