Given a big sorted array with positive integers sorted by ascending order. The array is so big so that you can not get the length of the whole array directly, and you can only access the kth number byArrayReader.get(k)(or ArrayReader->get(k) for C++). Find the first index of a target number. Your algorithm should be in O(log k), where k is the first index of the target number.

Return -1, if the number doesn't exist in the array.

Notice

If you accessed an inaccessible index (outside of the array), ArrayReader.get will return2,147,483,647.

Have you met this question in a real interview?

Yes

Example

Given[1, 3, 6, 9, 21, ...], and target =3, return1.

Given[1, 3, 6, 9, 21, ...], and target =4, return-1.

Challenge
O(log k), k is the first index of the given target number.

Solution: 1.初始化endindex=1 2.通过循环扩大endindex by 公式 endindex*2+1 直到找到包括target 的index

   public int searchBigSortedArray(int[] nums, int target)
        {
            // write your code here
            int endIndex = 1;

            while (nums[endIndex - 1] < target) {
                endIndex = endIndex * 2 + 1;
            }
            int start = 0, end = endIndex;
            while (start + 1 < end) {
                int mid = start + (end - start) / 2;

                if (nums[mid] == target)
                {
                    return mid;
                }
                else if (nums[mid] < target)
                {
                    start = mid;
                }
                else {
                    end = mid;
                }
            }
            if (nums[start] == target) {
                return start;
            }
            if (nums[end] == target){
                return end;
            }
            return -1;
        }