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

2026-09-13 HGNULB 约 4 分钟

文章信息 2 个分类 3 个标签

分类

LeetCode 中等

题目描述

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

题意分析

只能通过平台提供的 ArrayReader.get(index) 访问一个递增数组，长度未知。找到 target 返回下标，否则返回 -1。

越界读取会返回 2147483647，题目中的真实元素和目标都小于这个哨兵。可以把数组末尾以后的值看成无限大，这样仍保持单调，关键是先找到一个足够大的右边界，而不是逐项数出真实长度。

解法：倍增确定范围，再二分查找

核心思路

[!blue]

从闭区间 [0, 1] 开始检查右端。若 reader.get(right) < target，由于数组递增，下标不超过 right 的元素都不可能是目标，可以令 left = right + 1，再把右端扩大到原来的两倍。

扩展到右端值不小于目标时停止。此时左边界之前的值都已被排除，右端又已经达到或越过目标可能出现的位置，所以目标若存在，一定在 [left, right] 中。右端值大于目标只说明范围足够，不能直接判定目标不存在。

接下来做普通闭区间二分：中间值小于目标就舍弃左半边，大于目标就舍弃右半边，相等则返回下标。读到越界哨兵时会进入“大于目标”的分支，自动把范围向真实数组方向缩小，无需专门求出长度。

倍增让每次探测的范围成倍增长，减少接口调用。代码对右端翻倍设置了整数上限，中点则使用 left + (right - left) / 2，避免边界计算本身发生溢出。

解题步骤

初始化 left = 0、right = 1，保留下标零作为候选。

只要右端值小于目标，就排除旧右端及其左侧，再扩大右边界。

在确定的闭区间内二分，每次比较后排除已经确认不等于目标的中点。

相等时返回下标；直到 left > right 仍未找到时返回 -1。数组末尾之外的候选会由哨兵比较自然排除。

代码实现

class Solution {
    public int search(ArrayReader reader, int target) {
        int left = 0;
        int right = 1;

        while (reader.get(right) < target) {
            left = right + 1;
            right = right > Integer.MAX_VALUE / 2 ? Integer.MAX_VALUE : right * 2;
        }

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int value = reader.get(mid);

            if (value == target) {
                return mid;
            }

            if (value < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

func search(reader *ArrayReader, target int) int {
    left, right := 0, 1
    const maxIndex = 1<<31 - 1
    for reader.get(right) < target {
        left = right + 1
        if right > maxIndex/2 {
            right = maxIndex
        } else {
            right *= 2
        }
    }
    for left <= right {
        mid := left + (right-left)/2
        value := reader.get(mid)
        if value == target {
            return mid
        }
        if value < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

复杂度分析

时间复杂度：设目标在有序数组中的插入位置为 p，接口读取次数为 $O(\log(p + 2))$。倍增与随后区间内的二分都只需要对数次读取。

空间复杂度：$O(1)$，只保存边界、中点和读取值。

ArrayReader 由判题平台提供，Go 接口沿用平台的 get 方法。

关键点总结

[!green]

只有右端值仍小于目标时，才能排除这一段并继续扩展。

越界哨兵保持了比较的单调性，也保证扩展能够停止。

确定范围后仍需完整二分，右端超过目标不等于目标不存在。

易错点总结

[!yellow]

越界哨兵不是目标候选；依赖题目保证真实值与目标都小于它。

右边界倍增和中点计算都要避免整数溢出。

读到大于目标的值只能结束扩展，不能直接判定目标不存在。

相似题目

题目	难度	关联与区别
704. 二分查找	简单	边界确定后就是普通二分；本题额外用指数扩展寻找右边界。
35. 搜索插入位置	简单	目标缺失时仍有唯一插入边界，便于理解倍增范围为何能覆盖查找位置。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/50589150

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！