Search in a big sorted array

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 by ArrayReader.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.

It is still binary search, but how to start if we do not know the length?
Since there is a function t get kth element, we can do binary increase the first until we found a k whose element
is greater than target. we can then do normal binary search up to the k position.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

int binarySearch(int target){ int len = 1; while (ArrayReader.get(len - 1) < target){ len *= 2; } int low = 0, high = len - 1;//now we are working on 0 based index while (low <= high){ int mid = (low + high) / 2; int num = ArrayReader.get(mid); if (num <target) low = mid+1; else if(num>target)high = mid-1; else return mid; } return -1; }