Lintcode 447. Search in a Big Sorted Array

Given a big sorted array with non-negative integers sorted by non-decreasing 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

Example 1:

Input: [1, 3, 6, 9, 21, ...], target = 3
Output: 1

Example 2:

Input: [1, 3, 6, 9, 21, ...], target = 4
Output: -1

Challenge

O(logn) time, n is the first index of the given target number.

Notice

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

Code (Java):

/**
 * Definition of ArrayReader:
 * 
 * public class ArrayReader {
 * public int get(int index) {
 *          // return the number on given index, 
 *          // return 2147483647 if the index is invalid.
 *     }
 * };
 */
public class Solution {
    /*
     * @param reader: An instance of ArrayReader.
     * @param target: An integer
     * @return: An integer which is the first index of target.
     */
    public int searchBigSortedArray(ArrayReader reader, int target) {
        if (reader.get(0) == target) {
            return 0;
        }
        
        if (reader.get(0) > target) {
            return -1;
        }
        
        int end = 1;
        while (reader.get(end) < target) {
            end *= 2;
        }
        
        return binarySearch(reader, end / 2, end, target);
    }
    
    private int binarySearch(ArrayReader reader, int start, int end, int target) {
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            int midNum = reader.get(mid);
            if (midNum == target) {
                end = mid;
            } else if (midNum > target) {
                end = mid - 1;
            } else {
                start = mid + 1; 
            }
        }
        
        if (reader.get(start) == target) {
            return start;
        }
        
        if (reader.get(end) == target) {
            return end;
        }
        
        return -1;
    }
}

public class Solution {
    /**
     * @param reader: An instance of ArrayReader.
     * @param target: An integer
     * @return: An integer which is the first index of target.
     */
    public int searchBigSortedArray(ArrayReader reader, int target) {
        // write your code here
        // step 1: find the pos of the start and end index
        //
        int start = 0;
        int end = 0;

        while (reader.get(end) != Integer.MAX_VALUE && reader.get(end) < target) {
            start = end;
            end = end * 2 + 1;
        }

        // step 2: find the first idex of the target
        //
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            int num = reader.get(mid);
            if (num < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

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

        if (reader.get(end) == target) {
            return end;
        }

        return -1;
    }
}