Search in a Big Sorted Array

LeetCode LintCode

这道题还是属于二分法第二境界：
二分位置 之 OOXX

这里是在一个不知道size的big array里面找first index of a target number. 我最开始不知道要如何确定start和end, 视频里老师参考了java语言中ArrayList的resize，提出了倍增法。从index = 1开始，每次index * 2, 知道第 index 个数比target大，就可以把target 锁定在 index / 2 到index之间了。

/**
 * Definition of ArrayReader:
 * 
 * class ArrayReader {
 *      // get the number at index, return -1 if index is less than zero.
 *      public int get(int index);
 * }
 */
public class Solution {
    /**
     * @param reader: An instance of ArrayReader.
     * @param target: An integer
     * @return : An integer which is the index of the target number
     */
    public int searchBigSortedArray(ArrayReader reader, int target){
        int index = 1;
        while (reader.get(index) < target) {
            index *= 2;
        }
        int start = index / 2;
        int end = index;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (reader.get(mid) < target){
                start = mid;
            } else{
                end = mid;
            }
        }
        if (reader.get(start) == target){
            return start;
        }else if (reader.get(end) == target){
            return end;
        }else {
            return -1;
        }
    }
}

循环体结束后，只剩下三种可能， index = start的数是第一次出现target, index = end是第一次出现target, 没有target.