难度: Medium
Submission
运行时间: 27 ms
内存: 17.0 MB
# """
# This is ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
#class ArrayReader:
# def get(self, index: int) -> int:
class Solution:
def search(self, reader: 'ArrayReader', target: int) -> int:
left, right = 0, 1
# Double the right pointer until it exceeds the target value or goes out of bounds
while reader.get(right) < target:
left = right
right <<= 1
# Perform binary search between left and right
while left <= right:
mid = left + (right - left) // 2
num = reader.get(mid)
if num == target:
return mid
elif num < target:
left = mid + 1
else:
right = mid - 1
return -1
Explain
这个题解采用的是二分查找的思路。首先通过不断翻倍右指针的方式确定目标值可能所在的范围，直到右指针超出目标值或数组边界。然后在确定的范围内进行标准的二分查找，直到找到目标值或确定目标值不存在。
时间复杂度: O(log n)
空间复杂度: O(1)
class Solution:
def search(self, reader: 'ArrayReader', target: int) -> int:
left, right = 0, 1
# 不断翻倍右指针直到超过目标值或数组边界
while reader.get(right) < target:
left = right
right <<= 1
# 在确定的范围内进行二分查找
while left <= right:
mid = left + (right - left) // 2
num = reader.get(mid)
if num == target:
return mid
elif num < target:
left = mid + 1
else:
right = mid - 1
return -1
Explore
在初始阶段，右指针的翻倍增长是基于指数回退的思想，这种方法可以快速缩小目标值可能存在的范围。由于每次都是翻倍增长，即每次都将范围扩大到前一次的两倍，这保证了不会错过目标值。只要每次移动左指针到旧的右指针位置，就可以确保覆盖所有可能的位置。因此，这种增长速率既快速又安全，不会错过目标值。
在处理长度未知的数组时，`reader.get(right)`调用可能会越界。通常，数组读取接口会有一种机制来处理越界访问，比如返回一个特殊的值（如 Integer.MAX_VALUE 或某个错误代码），用来表示越界。在实现中，我们可以通过检查这个返回值来判断是否越界，并据此停止指数增长，将右边界设置为当前的越界位置的前一个位置。
在二分查找中，每次计算新的`mid`值后，会根据与目标值的比较结果调整左指针`left`或右指针`right`。如果`mid`值处的元素不是目标值，下一次搜索会排除当前`mid`位置。如果`mid`值小于目标值，则将`left`设置为`mid + 1`，反之则将`right`设置为`mid - 1`。这样，每次循环都会缩小搜索范围，避免重复访问已经检查过的索引。
当`left`和`right`很接近时，实际上搜索空间已经非常小。这时可以考虑直接对这个小范围的元素进行简单的线性搜索，因为此时线性搜索的成本与二分查找相当，但可以减少计算`mid`和多次比较的开销。此外，对于极小范围内的搜索，二分查找的优势不再明显，简单直接的线性搜索可能更有效率。