题目大意
#
给定一个升序数组 nums，但是数组的大小是未知的，只能通过接口 reader.get(k) 来获取数组 nums 中第 k 个元素值。如果数组访问越界，则接口返回 2147483647。再给定一个数字 target。要求从 nums 中找出 target，并返回下标，如果 nums 中不存在 target，则返回 -1。
解题思路
#
这道题的关键点在于找到数组的大小，以便确定查找的右边界位置。右边界可以通过倍增的方式快速查找。在查找右边界的同时，也能将左边界的范围进一步缩小。等确定了左右边界，就可以使用二分查找算法快速查找 target。
代码
#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
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)
|