2.3 Search in a Big Sorted Array

Search an sorted array which is too big to get length directly, can access kth number only by reader.get(k)

Example

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

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

Logical Steps

1. Do a reverse binary search looking for rough ending position
2. With that ending position, do binary search look for target position

Code Template

public int searchBigSortedArray(ArrayReader reader, int target) {
    if (reader.get(0) == -1)
        return -1;

    int start = 0;
    int end = 0;

    // find an end to start with
    while(reader.get(end) != -1 && reader.get(end)<target) {
        end = end * 2 + 1;
    }

    // binary search from start to end, search for target
    while(start + 1 < end) {
        int mid = (start+end)/2;
        /** REMEMBER, WHEN target == mid
         * LET end = mid INSTEAD OF RETURNING mid DIRECTLY
         * SINCE WE ARE LOOKING FOR FIRST MATCHING POSITION
         * NEED TO CONSIDER MULTIPLE TARGET VALUE IN INPUT
         */
        if (target > reader.get(mid)) {
            start = mid;
        }else{
            end = mid;
        }
    }


    // figure out its start, end or not at all
    // ascending order, so start with end
    if (target == reader.get(end))
        return end;

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

    return -1;
}

Common Mistakes

1. When looking for rough ending position, end = end 2 instead of end = end 2 + 1

    int end = 0;
    /** this is a mistake example
    * remenber end = 0, 0*2 will always be 0
    */
    while(reader.get(end) != -1 && reader.get(end)<target) {
        end = end * 2;
    }
   

2. When target == reader.get(mid), return mid directly. Same as basic binary search, when there are multiple input element, we need to return the first position. So, it should be end = mid in this case