Thinking process

• find the first position at which the value is target
• but how to find the end position if I'm going to do the binary search
  • double the initial end position if its value is smaller than target

Mistakes

• the end position should include the value that is equal to target

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) {
        //find a number that is larger than target
        int start = 0;
        int end = 1;

        while (reader.get(end) <= target) {
            end *= 2;
        }

        //binary search
        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;

            if (reader.get(mid) < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (reader.get(start) == target) return start;
        if (reader.get(end) == target) return end;

        return -1;
    }
}