Home Computer Science Java Algorithm

447 · Search in a Big Sorted Array - LintCode

# Description

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.

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

# 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.

# Solution

因為無法 get 到 big array 的 length, 可以用倍增法

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) {
        int kth = 1;
        //get kth 的 index, 所以記得 - 1
        while (reader.get(kth - 1) < target) {
            // 這裡增兩倍
            kth = kth * 2; 
        }
        int start = 0, end = kth - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (reader.get(mid) < target) {
                start = mid;
            } else {
	            // 找 first index, 當 mid == target 也未必是 first index
                end = mid;
            }
        }
        if (reader.get(start) == target) {
            return start;
        }
        if (reader.get(end) == target) {
            return end;
        }
	
        return -1;
    }
}