447 · 在大数组中查找

Difficulty

Medium

Tags

二分查找

URL

https://www.lintcode.com/problem/447/description

Star

给一个按照升序排序的非负整数数组。这个数组很大以至于你只能通过固定的接口 ArrayReader.get(k) 来访问第k个数(或者C++里是ArrayReader->get(k))，并且你也没有办法得知这个数组有多大。

找到给出的整数target第一次出现的位置。你的算法需要在O(logk)的时间复杂度内完成，k为target第一次出现的位置的下标。

如果找不到target，返回-1。

如果你访问了一个不可访问的下标（比如越界），ArrayReader 会返回2,147,483,647。

样例

样例 1:


输入: [1, 3, 6, 9, 21, ...], target = 3
输出: 1

样例 2:


输入: [1, 3, 6, 9, 21, ...], target = 4
输出: -1

二分查找

思路

题目的难点在于搜索范围的右边界无从得知，所以先通过倍增的思想开找到右边界，然后再利用常规二分思想查找target的左边界

题解


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
        # 先倍增找到右边界
        right = 1
        while reader.get(right) < target:
            right *= 2
        # 此时左边界即为右边界的一半
        left = right // 2

        while left <= right:
            mid = left + (right- left) // 2
            temp = reader.get(mid)
            if temp < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return left if reader.get(left) == target else -1

447 · 在大数组中查找 - LintCode

二分查找