Search in a Big Sorted Array

Question

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). If you accessed an inaccessible index (outside of the array), ArrayReader.get will return 2,147,483,647.

Example

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

Analysis

Use a binary increment to find an end > target. Then find the first position of the target.

Code

public int searchBigSortedArray(ArrayReader reader, int target) {
    // use log increment to find an end first
    int index = 1;
    while (reader.get(index - 1) < target) {
        index = index * 2;
    }
    // find first pos of target
    int start = 0, mid, end = index - 1;
    while (start + 1 < end) {
        mid = start + (end - start) / 2;
        if (reader.get(mid) == target) {
            end = mid;
        } else if (reader.get(mid) < target) {
            // median < target, search right section
            start = mid + 1;
        } else {
            // median > target, search left section
            end = mid - 1;
        }
    }
    if (reader.get(start) == target) {
        return start;
    } else if (reader.get(end) == target) {
        return end;
    } else {
        return -1;
    }
}