LeetCode 面试题 10.05. 稀疏数组搜索

2026-05-24 HGNULB 约 10 分钟

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

分类

LeetCode CodeTop 简单未解决 1-2 拼多多程序员面试金典（第 6 版）

题目描述

✅ 面试题 10.05. 稀疏数组搜索

题意分析

给定一个按字典序排好序的字符串数组 words，其中散布着一些空字符串，要求找出目标串 s 所在的下标，不存在则返回 -1。所谓"排好序"，指的是忽略那些空串之后，剩下的非空串是字典序非递减的；空串本身可以出现在任意位置。

约束里最关键的信号有两个。第一，数组是有序的，这是在明示要用二分而不是线性扫描。第二，空串会打断有序性——如果直接拿 words[mid] 去和 s 比较，mid 落在空串上时得到的比较结果毫无意义：空串字典序最小，无论 s 是什么都会得出"该往右找"的结论，可答案完全可能在左边。所以标准二分的判定函数在空串处失效，必须先想办法把 mid "挪"到一个有意义的位置。

边界上要覆盖：s 本身是空串（题目要求返回 -1，因为空串不构成有效目标）；整个数组全是空串；mid 到区间右端全是空串（此时右边给不出任何信息）；以及目标不存在时的正常收尾。

解法：二分查找判定答案

核心思路

暴力做法是从左到右扫一遍找相等的串，$O(n)$ 次字符串比较。它一定正确，但完全没用上"有序"这个条件——面试官出这题就是想看你怎么在有序性被空串破坏的情况下，还能把二分用起来。

二分能成立，靠的是"比较 words[mid] 和 s 之后能排除掉一整边"。问题出在 words[mid] 可能是空串，此时这次比较不携带任何关于 s 位置的信息。关键观察是：空串虽然不能用来做判定，但它左右两侧的非空串仍然是有序的——只要把探针从 mid 出发向右挪到第一个非空串 probe，words[probe] 就是一个合法的判定点，而且它和 s 的比较结果依然能排除掉一整边。

由此定义搜索状态：闭区间 [lo, hi] 表示"s 若存在，必定落在这个下标范围内"，这就是全程要维持的不变量。每轮循环取中点 mid，然后：

向右探测：从 mid 起找到第一个非空下标 probe（探测范围限制在 hi 以内）。

若 probe > hi，说明 [mid, hi] 这一整段全是空串，右边给不出任何信息，也不可能藏着 s（s 非空），于是把区间收缩成 [lo, mid - 1]。注意收缩到 mid - 1 而不是 probe - 1，因为 [mid, hi] 已被整体排除，右端点退到 mid 之前即可。

否则用 words[probe] 与 s 比较：相等就返回 probe；words[probe] < s 说明 s 只可能在 probe 右侧，令 lo = probe + 1；words[probe] > s 说明 s 只可能在 mid 左侧（注意是 mid 不是 probe，因为 [mid, probe] 之间全是空串、不可能是答案），令 hi = mid - 1。

每一轮都严格砍掉至少一个元素（lo 至少推进到 mid + 1 之后，或 hi 至少退到 mid - 1），所以循环必然终止。区间空掉仍未命中，就返回 -1。

为什么向右探测而不是向左？两个方向都正确，选右边是为了让"排除逻辑"更简单：向右探测时，被跳过的 [mid, probe-1] 全是空串，无论比较结果往哪边收缩，这一段都被顺带排除掉了；若向左探测则要额外注意 lo 的更新不能越过探针。实现上还可以两侧同时向外探测取更近的那个，常数更好，但代码复杂度上升，面试里单向探测已经足够。

复杂度上，正常情况下每轮区间减半、探测只走几步，是 $O(\log n)$ 次比较；但最坏情况（数组几乎全是空串）探测本身就要走 $O(n)$ 步，整体退化成 $O(n)$。这是空串带来的本质代价，面试里要主动说明"没有对数级的最坏保证"。

解题步骤

初始化 lo = 0、hi = words.length - 1，用闭区间表示待搜索范围。空数组时 hi = -1，循环条件 lo <= hi 直接不成立，返回 -1，不需要额外特判。

循环条件写 lo <= hi。闭区间下 lo == hi 时区间里还有一个元素必须检查，写成 < 会漏掉最后一个候选。

取 mid = lo + (hi - lo) / 2，避免 lo + hi 溢出。

从 mid 向右探测第一个非空串，探测边界是 hi。条件写成 probe <= hi && words[probe].isEmpty()：先判越界再取值，且探测不能越过 hi——越过就是在读区间外的数据，那些下标已经被前几轮排除，用它们做判定会破坏不变量。

探测失败（probe > hi）时令 hi = mid - 1 并进入下一轮。这一步是"[mid, hi] 全空 → 整段排除"的落地。因为 s 非空，空串段里绝不可能是答案；而这段之外的信息本轮拿不到，只能缩小到左边继续。

探测成功后用 words[probe] 做三路比较。相等直接返回 probe——注意返回的是探针位置而不是 mid，mid 上可能是空串。小于时 lo = probe + 1：probe 以及它左边的整段（含空串）都被排除。大于时 hi = mid - 1：probe 右边的都更大所以出局，[mid, probe] 是空串也出局，剩下的只有 mid 左边。

循环结束返回 -1。此时不变量保证"若 s 存在必在区间内"，而区间已空，所以不存在。

以 words = ["at", "", "", "", "ball", "", "", "car", "", "", "", "dad", "", ""]（下标 0..13）、s = "ball" 走一遍：

第 1 轮：lo = 0，hi = 13，mid = 6。words[6] 是空串，探针右移到 probe = 7，words[7] = "car"。比较 "car" > "ball"，说明答案在 mid 左边，令 hi = mid - 1 = 5。区间变成 [0, 5]。

第 2 轮：lo = 0，hi = 5，mid = 2。words[2] 是空串，探针右移：words[3] 仍空，probe = 4，words[4] = "ball"。比较相等，返回 4，正确。

注意第 1 轮里 hi 被设成 5 而不是 probe - 1 = 6：两者都正确（下标 6 是空串，留着也不会被误判），设成 mid - 1 是更保守也更好证明的写法。

再以 words = ["at", "", ""]、s = "at" 走一遍，覆盖"探测失败"分支：

第 1 轮：lo = 0，hi = 2，mid = 1。words[1] 空，probe = 2 仍空，probe = 3 已经 > hi，探测失败。令 hi = mid - 1 = 0，区间变成 [0, 0]。

第 2 轮：mid = 0，words[0] = "at" 非空，比较相等，返回 0，正确。如果探测失败时误写成 lo = mid + 1（往右缩），区间会变成 [2, 2]，第二轮读到空串再次探测失败，最终返回 -1，答案就丢了。

最后看 s = "" 的边界：第 1 轮 probe 指向的任何非空串都大于空串，比较结果恒为"大于"，hi 不断左移直到区间为空，返回 -1，符合题目要求。

代码实现

class Solution {
    public int findString(String[] words, String s) {
        int lo = 0;
        int hi = words.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int probe = mid;
            while (probe <= hi && words[probe].isEmpty()) {
                probe++;
            }
            if (probe > hi) {
                hi = mid - 1;
                continue;
            }
            int cmp = words[probe].compareTo(s);
            if (cmp == 0) {
                return probe;
            } else if (cmp < 0) {
                lo = probe + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }
}

func findString(words []string, s string) int {
    lo, hi := 0, len(words)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        probe := mid
        for probe <= hi && words[probe] == "" {
            probe++
        }
        if probe > hi {
            hi = mid - 1
            continue
        }
        if words[probe] == s {
            return probe
        } else if words[probe] < s {
            lo = probe + 1
        } else {
            hi = mid - 1
        }
    }
    return -1
}

复杂度分析

时间复杂度：平均 $O(\log n \cdot L)$，最坏 $O(n \cdot L)$，其中 L 为字符串平均长度（一次字符串比较不是 $O(1)$）。区间每轮至少减少一个元素、正常情况下减半，所以是对数轮；但当数组中空串极多（极端情况全为空串）时，单轮的向右探测就要走 $O(n)$ 步，退化成线性。

空间复杂度：$O(1)$。只用了 lo、hi、mid、probe 四个下标变量，是纯迭代实现，没有递归栈也没有辅助数组。

关键点总结

二分的前提不是"数组有序"，而是"存在一个能排除半边的判定"。本题数组确实有序，但空串处的比较不携带信息，判定失效——先确认判定在每个可能的 mid 上都有意义，再动手写二分。

判定点失效时，把探针挪到最近的有效位置，而不是放弃二分。这是一类可迁移的修补手法：mid 不可用就向一侧线性探测到可用点，用它做判定，同时把跳过的那段一并排除。代价是最坏复杂度退化，但平均情况仍保留二分的优势。

收缩边界时要区分"探针位置"和"中点位置"。向右探测后，若判定结果是"往左找"，右边界必须退到 mid - 1 而不是 probe - 1；若是"往右找"，左边界推进到 probe + 1。搞混这两个下标是本题最隐蔽的错误来源。

"整段无效"要有独立的处理分支。[mid, hi] 全是空串时，这一轮拿不到任何判定信息，唯一安全的动作是把区间整体缩到左边。缺了这个分支，循环会因为 lo、hi 不更新而死循环。

面试视角：主动交代最坏复杂度并给出改进方向。面试官几乎必问"全是空串时你的算法多快"。标准答法是：最坏 $O(n)$，因为探测本身是线性的；若追求更好的常数可以从 mid 向左右同时探测取更近的非空位置；但只要空串比例不受限，就不存在 $O(\log n)$ 的最坏保证。能主动说清这一点，比写出代码更能体现对二分适用边界的理解。

易错点总结

错误写法：不做探测，直接拿 words[mid] 与 s 比较 → 用例 words = ["at", "", "", "", "ball"]、s = "at"：mid = 2 是空串，"" < "at" 得出"往右找"，令 lo = 3，此后再也回不到下标 0，返回 -1，正确答案是 0。

错误写法：探测时不限制上界，写成 while (words[probe].isEmpty()) probe++; → 用例 words = ["at", "", ""]、s = "at"：第一轮 mid = 1 起探测，probe 一路走到 3 时数组越界抛异常（Go 里是 panic）。探测条件必须先判 probe <= hi。

错误写法：探测越过 hi 但仍用区间外的 words[probe] 做判定 → 用例 words = ["a", "", "z"]、s = "a"，且某轮区间已收缩到 [0, 1]：探针跑到下标 2 拿 "z" 比较，得出"往左"结论虽然凑巧不错，但下标 2 早已被排除，用它做判定破坏了不变量，在别的数据上会得出错误的收缩方向。

错误写法：探测失败时写成 lo = mid + 1 → 用例 words = ["at", "", ""]、s = "at"：区间从 [0, 2] 变成 [2, 2]，下标 0 上的答案被跳过，返回 -1，正确答案是 0。整段空串意味着答案只可能在左边。

错误写法：探测失败时不更新 lo/hi 直接 continue → 用例 words = ["", ""]、s = "a"：mid 恒为 0、探测恒失败、区间恒不变，死循环直到超时。

错误写法：命中时返回 mid 而不是 probe → 用例 words = ["at", "", "", "", "ball", "", "", "car", "", "", "", "dad", "", ""]、s = "ball"：第二轮 mid = 2 是空串、probe = 4 命中，返回 2，正确答案是 4。

错误写法：words[probe] > s 时写成 hi = probe - 1，同时又把探测方向改成向左 → 混用两个方向后，向左探测得到的 probe 小于 mid，再令 hi = probe - 1 会把 [probe, mid] 里可能的答案一并砍掉；用例 words = ["a", "", "b"] 上会漏解。探测方向和边界更新必须成套使用。

错误写法：Java 里用 words[probe] == s 比较字符串 → 用例 words = ["at"]、s = new String("at")：比较的是引用地址而非内容，返回 -1。Java 必须用 equals 或 compareTo。

错误写法：words[probe].isEmpty() 写成 words[probe] == null → 用例 words = ["at", "", ""]：空串不是 null，探测条件恒为假，探针停在空串上做比较，退化成第一条错误。

错误写法：为 s 是空串加一条 if (s.isEmpty()) return -1; 之外，还加了 if (words.length == 0) return -1; 却把它写在取 words[0] 之后 → 用例 words = []：先访问 words[0] 就已经越界。空数组应当由 hi = -1 与循环条件自然接住，任何提前访问都要放在判空之后。

错误写法：改成递归分治，先无条件搜左半再搜右半 → 用例 n = 10^5 的稀疏数组：这种写法访问了每一个下标，本质是打乱顺序的线性扫描，复杂度恒为 $O(n)$，完全没用上有序性；虽然能通过判题，但在面试里等于没有回答"如何二分"这个问题。

相似题目

题目	难度	考察点
704. 二分查找	简单	判定处处有效的标准模板，用来对照本题探针修补的必要性
面试题 08.03. 魔术索引	简单	同样是有序但判定失效，修补方式是区间剪枝而非探针右移
34. 在排序数组中查找元素的第一个和最后一个位置	中等	判定完好但要定位边界，考的是左右开闭区间与收缩方向的配套
81. 搜索旋转排序数组 II	中等	重复元素让"哪半边有序"无法判定，处理办法是收缩端点而非探测
1095. 山脉数组中查找目标值	困难	先二分峰顶把数组切成两段单调区间，再分别二分，且访问次数受限