如何在无限数组中利用二分查找定位目标键的位置

首先明确前提：能通过二分思路解决的无限数组查找问题，默认数组是单调有序的（一般默认升序），无序无限数组不存在高效查找方案，因为你永远无法确认未遍历的后续位置是否存在目标。

核心思路很简单：既然没法提前拿到数组总长度确定二分边界，就先动态扩张边界，先锁定包含目标值的确定区间，再在这个区间内执行标准二分查找即可。

具体执行步骤 #

• 初始化极小的初始边界：左边界设为索引0，右边界设为索引1即可，不需要预设大初始值。
• 指数级扩张右边界：循环判断当前右边界位置的元素和目标值的大小，如果当前右边界的元素小于目标值，说明目标在更靠右的位置，此时把左边界移动到原右边界位置，右边界直接翻倍（用指数步长扩张是为了保证找边界的效率，不会退化成线性遍历）。
• 区间内二分：当找到第一个右边界位置的元素大于等于目标值时，[left, right]就是确定包含目标的有效区间（目标存在的前提下），直接在这个固定长度区间执行标准二分查找即可定位目标位置。

边界说明：如果数组是降序排列，只需要把扩张边界的判断条件反过来即可，核心逻辑不变。

参考实现（Python） #

def search_infinite_sorted_array(arr, target):
    # 初始化初始查找边界
    left = 0
    right = 1
    # 指数扩张，锁定包含目标的区间
    while arr[right] < target:
        left = right
        right *= 2
    # 锁定区间后执行标准二分查找
    while left <= right:
        # 用这种写法计算mid避免整数溢出
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    # 目标不存在时返回-1
    return -1

复杂度说明 #

整个过程的时间复杂度和已知长度的普通二分一致，为O(log k)，其中k是目标值所在的索引位置：

• 边界扩张阶段每次右边界翻倍，最多需要log₂k次就能覆盖到目标位置
• 锁定后的区间长度最大为k，二分查找的时间消耗同样为O(log k)
  整体没有量级上的性能损耗。

内容的提问来源于stack exchange，提问作者niyon01