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.

If you accessed an inaccessible index, ArrayReader.get would return -1.

Return -1, if the number doesn't exist in the array.

Thoughts

大数据风吹来的一道题。思路是当搜索范围非常大时，直接把end设成length-1会造成浪费，不如逐步增大end.

不过我偷懒直接用普通bin search也过了，所以代码不用看哈。。

Code

public class Solution {
    /**
     * @param A: An integer array
     * @param target: An integer
     * @return : An integer which is the index of the target number
     */
    public int searchBigSortedArray(int[] nums, int target) {
        if (nums.length == 0) {
            return -1;
        } 
        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                end = mid;
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }

        return -1;
    }
}

Analysis

复杂度依然是O(lgn), 大O是描述最坏情况。