雅虎面试题-无限排序数组查找

You are given an infinite array A[] in which the first n cells contain integers in sorted order and the rest of the cells are filled with ∞. You are not given the value of n. Describe an algorithm that takes an integer x as input and finds a position in the array containing x, if such a position exists, in O(log n) time.
意思：
给定一个数组A[ ]，包含无限个元素，前n个元素是排好序的，后面的值全部是无穷大。找到给定的目标x，如果x存在于前n个元素中，返回其索引。
要求时间复杂度是logn.
例子：
{1,2,3,4,7,9,11,18,20,31,36,65,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE}
如果找24，则找不到，返回-1。
如果找31，则找到，返回其索引9。

Solution:
排好序的数组，并且查找复杂度logN,可以立即想到要用二分查找。

关键是这个无限大的数组，不知道右边的边界。所以要确定右边界，并且总体时间复杂度也不能超过logN。
logN 可以想象为树的层数的概念，每层节点数是2^i，这样子每次以该量级递增，则复杂度是logN.
那么使用位置1，2，4，8，16。。。依次判断数组的该位置是否是MAX_VALUE，碰到就停止。这样就可以保证log级别的复杂度找到边界。

代码实现:

public class FindKIndexFromInfinteArray {
    public static int solution(int[] array, int target){
        int result = -1;
        // 处理边界与特殊值
        if(array == null || array.length == 0)    return result;
        if(array[0] == Integer.MAX_VALUE)    return result;
        else if(array[0] == target)    return 1;

        int i = 1;
        while(array[i] != Integer.MAX_VALUE){// 遇到MAX就停止
            if(array[i] == target)    return i;// 在循环中如果碰到刚好等于目标值，就直接返回
            i *= 2;//2，4，8，16，32。。。以指数级别上升
        }
        // 此时i定位到一个右边界，开始进行二分查找，从0到i
        result = binarySearch(array, target, 0, i);
        return result;
    }
    /** 二分查找*/
    private static int binarySearch(int[] array, int target, int low, int high) {
        int left = low, right = high - 1;
        /* 如果这里是 int right = n 的话，那么下面有两处地方需要修改，以保证一一对应：
         * 1、下面循环的条件则是while(left < right)
         * 2、循环内当array[middle]>value 的时候，right = mid
         */
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(array[mid] > target)        right = mid - 1;
            else if(array[mid] < target)    left = mid + 1;
            else    return mid;
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,7,9,11,18,20,31,36,65,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE};
        System.out.println(solution(nums, 31));
    }
}