Search in a Big Sorted Array

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 firstElement = reader.get(0);
        if (firstElement == target) 
            return 0;
        else if (firstElement > target)
            return -1;
        
        int idx = 0, jump = 1;
        while (jump != 0) {
            while (jump != 0 && reader.get(idx + jump) < target)   
                idx += jump;
                jump >>= 1;
            jump <<= 1; 
        }
        
        if (reader.get(idx + 1) == target)
            return idx + 1;
        else
            return -1;
    }
}

class Solution:
    """
    @param: reader: An instance of ArrayReader.
    @param: target: An integer
    @return: An integer which is the first index of target.
    """
    def searchBigSortedArray(self, reader, target):
        # write your code here
        start = 0
        #end should be larger than target
        end = 1
        while reader.get(end) < target:
            end = end * 2
        
        while start+1 < end:
            mid = (start+end)//2
            if target <= reader.get(mid):
                end = mid
            else:
                start = mid
        if reader.get(start) == target:
            return start
        elif reader.get(end) == target:
            return end
        else:
            return -1

上一页Find K Closest Elements 下一页Fast Power

最后更新于5年前

这有帮助吗？