跳至主要內容

0702. 搜索长度未知的有序数组

ITCharge大约 2 分钟

0702. 搜索长度未知的有序数组open in new window

  • 标签:数组、二分查找、交互
  • 难度:中等

题目链接

题目大意

描述:给定一个升序数组 secretsecret,但是数组的大小是未知的。我们无法直接访问数组,智能通过 ArrayReader 接口去访问他。我们可以通过接口 reader.get(k)

  1. 如果数组访问未越界,则返回数组 secretsecret 中第 kk 个下标位置的元素值。
  2. 如果数组访问越界,则接口返回 23112^{31} - 1

现在再给定一个数字 targettarget

要求:从 secretsecret 中找出 secret[k]==targetsecret[k] == target 的下标位置 kk,如果 secretsecret 中不存在 targettarget,则返回 1-1

说明

  • 1secret.length1041 \le secret.length \le 10^4
  • 104secret[i],target104-10^4 \le secret[i], target \le 10^4
  • secretsecret 严格递增。

示例

  • 示例 1:
输入: secret = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 存在在 nums 中,下标为 4
  • 示例 2:
输入: secret = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不在数组中所以返回 -1

解题思路

思路 1:二分查找算法

这道题的关键点在于找到数组的大小,以便确定查找的右边界位置。右边界可以通过倍增的方式快速查找。在查找右边界的同时,也能将左边界的范围进一步缩小。等确定了左右边界,就可以使用二分查找算法快速查找 targettarget

思路 1:代码

class Solution:
    def binarySearch(self, reader, left, right, target):
        while left < right:
            mid = left + (right - left) // 2
            if target > reader.get(mid):
                left = mid + 1
            else:
                right = mid
        if reader.get(left) == target:
            return left
        else:
            return -1

    def search(self, reader, target):
        left = 0
        right = 1
        while reader.get(right) < target:
            left = right
            right <<= 1

        return self.binarySearch(reader, left, right, target)

思路 1:复杂度分析

  • 时间复杂度O(logn)O(\log n),其中 nn 为数组长度。
  • 空间复杂度O(1)O(1)