LeetCode 702. Search in a Sorted Array of Unknown Size 2019-08-20

题目描述

给定一个升序整数数组,写一个函数搜索 nums 中数字 target。如果 target 存在,返回它的下标,否则返回 -1。注意,这个数组的大小是未知的。你只可以通过 ArrayReader 接口访问这个数组,ArrayReader.get(k) 返回数组中第 k 个元素(下标从 0 开始)。

你可以认为数组中所有的整数都小于 10000。如果你访问数组越界,ArrayReader.get 会返回 2147483647。

tag

二分

样例

1
2
3
4

输入: array = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 存在在 nums 中,下标为 4

算法1

(二分) O(logn)
思路
复杂度分析:
python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def search(self, reader, target):
"""
:type reader: ArrayReader
:type target: int
:rtype: int
"""
left = 0
right = 20000

while left < right:

mid = (left + right) // 2

if reader.get(mid) == 2147483647:
right = mid
elif reader.get(mid) >= target:
right = mid
else:
left = mid + 1

if reader.get(left) == target:
return left
return -1