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.

Example:

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

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

Solution:

Assume we have a number x = 1, we double it and compare with target until x is greater than target. Then we know the target sits between last x and current x. Since it finds the first index of a target number, we need to use the same approach in First Position of Target.

Code:

public int searchBigSortedArray(ArrayReader reader, int target) {
    if (reader == null) {
        return -1;
    }
    int idx = 1;
    while (reader.get(idx - 1) < target) {
        idx = idx * 2;
    }
    int start = idx / 2;
    int end = idx;
    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;
    }
    if (reader.get(end) == target) {
        return end;
    }
    return -1;
}