LeetCode 面试题 08.03. 魔术索引

2026-03-27 HGNULB 约 11 分钟

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

分类

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

题目描述

✅ 面试题 08.03. 魔术索引

题意分析

在一个有序（非递减）整数数组 nums 中，若存在下标 i 使得 nums[i] == i，则称 i 是一个"魔术索引"。要求返回最小的魔术索引，不存在则返回 -1。

约束里最要命的一句是"数组元素可能有重复"。如果元素严格递增，函数 f(i) = nums[i] - i 是严格单调递增的，f(i) == 0 的位置唯一且可以用标准二分在 $O(\log n)$ 内找到；一旦允许重复，相邻两项满足 f(i+1) - f(i) = (nums[i+1] - nums[i]) - 1 >= -1，也就是说 f 可以任意上升、也可以每步下降 1，完全失去单调性。没有单调性，就不能靠 f(mid) 的符号丢掉半边区间。

第二个信号是题目要"最小的魔术索引"。这意味着即使在右半边先找到一个答案，也必须确认左半边确实没有更小的，所以搜索顺序必须是"左优先"，找到就立刻返回。

边界上要覆盖：空数组（返回 -1）；nums[0] == 0 这种答案在最左端的情形；全部元素相等（如 [1, 1, 1]）；元素为负数导致 nums[mid] < mid 的剪枝方向；以及完全没有魔术索引的情形。

解法：递归二分 + 剪枝（先左后右）

核心思路

暴力做法是从左到右扫一遍，第一个满足 nums[i] == i 的就返回。它是 $O(n)$、绝对正确，而且因为从左往右扫，天然满足"最小"的要求。瓶颈在于：数组明明有序，这个信息一点没用上，面试官出这题就是想看你能不能利用有序性。

但如上所述，重复元素让 nums[i] - i 失去单调性，标准二分直接丢半边区间是错的。举个反例：nums = [-10, -5, 2, 2, 2, 3, 4, 7, 9, 12]，mid = 4 时 nums[4] = 2 < 4，按"nums[mid] < mid 就只搜右边"的标准二分逻辑会把左半边整个丢掉，可答案恰恰是左半边的下标 2（nums[2] = 2）。一个反例就足以把朴素二分打穿。

真正能用的观察是一条剪枝性质：数组非递减，意味着从 mid 往左走时，nums 的值只会不增，而下标每退一步就减 1。所以对于任意 j < mid，有 nums[j] <= nums[mid]；若要 nums[j] == j，必须 j <= nums[mid]。也就是说：

\[\text{左半边的搜索范围可以从 } [lo,\ mid-1] \text{ 收缩到 } [lo,\ \min(mid-1,\ nums[mid])]\]

对称地，对于任意 j > mid，有 nums[j] >= nums[mid]；若要 nums[j] == j，必须 j >= nums[mid]，于是：

\[\text{右半边的搜索范围可以从 } [mid+1,\ hi] \text{ 收缩到 } [\max(mid+1,\ nums[mid]),\ hi]\]

由此定义递归函数 dfs(lo, hi)：返回 nums 在下标区间 [lo, hi] 内最小的魔术索引，没有则返回 -1。递归体的顺序是先左、再中、后右——这个顺序不是随意的，它正好是下标从小到大的顺序，第一个返回的非 -1 结果就是全局最小，可以立刻向上层短路返回，无需比较。

最坏情况（如全部元素相等）剪枝完全失效，两侧都要递归，复杂度退化成 $O(n)$，与暴力同阶；但在元素分布"正常"时剪枝会砍掉大量区间，实际表现远好于线性扫描。这也是面试里该说清的一句话：这是一个有最坏保证的剪枝搜索，不是真正的 $O(\log n)$ 二分，重复元素的存在从根本上决定了没有对数解。

解题步骤

入口调用 dfs(nums, 0, n - 1)，用闭区间表示待搜索范围。空数组时 hi = -1，第一条终止条件就把它接住返回 -1，不需要额外特判。

递归第一步：lo > hi 返回 -1。表示区间为空、找不到答案。必须是 > 而不是 >=，因为 lo == hi 时区间里还有一个元素需要检查。

取 mid = lo + (hi - lo) / 2。写成这个形式避免 lo + hi 溢出。mid 取哪里其实不影响正确性（先左后右保证了不漏解），取中点只是让剪枝的期望效果最好。

先递归左半边：dfs(lo, min(mid - 1, nums[mid]))。必须先左，因为要的是最小索引；一旦左边返回了非 -1，它一定小于 mid 和右半边的任何答案，直接返回即可，无需再看后面。上界取 min 是剪枝：下标大于 nums[mid] 的位置在左半边不可能相等（那里的值只会更小或相等，而下标更大）。

左边无解，再检查 mid 本身：nums[mid] == mid 就返回 mid。这一步必须放在左递归之后、右递归之前，才符合"下标从小到大"的检查顺序。

最后递归右半边：dfs(max(mid + 1, nums[mid]), hi)。下界取 max 是对称的剪枝：下标小于 nums[mid] 的位置在右半边不可能相等（那里的值只会更大或相等，而下标更小）。直接返回它的结果，因为此时左边和 mid 都已排除。

以 nums = [-1, 0, 2] 走一遍（下标 0..2，答案应为 2）：

dfs(0, 2)：mid = 1，nums[1] = 0。左半边上界 min(0, 0) = 0，递归 dfs(0, 0)。

dfs(0, 0)：mid = 0，nums[0] = -1。左半边上界 min(-1, -1) = -1，递归 dfs(0, -1)，lo > hi 返回 -1。检查 nums[0] == 0？-1 != 0，不是。右半边下界 max(1, -1) = 1，递归 dfs(1, 0)，lo > hi 返回 -1。整体返回 -1。

回到 dfs(0, 2)：左边无解；检查 nums[1] == 1？0 != 1，不是。右半边下界 max(2, 0) = 2，递归 dfs(2, 2)。

dfs(2, 2)：mid = 2，nums[2] = 2。左半边上界 min(1, 2) = 1，递归 dfs(2, 1) 返回 -1。检查 nums[2] == 2？成立，返回 2。

最终返回 2，正确。注意 max(2, 0) = 2 这一步：如果不取 max 而直接用 mid + 1 = 2，结果相同；但换成 nums[mid] 更大的数组时，max 能一次跳过一大段。

再以 nums = [1, 1, 1] 走一遍（有重复元素，答案应为 1）：

dfs(0, 2)：mid = 1，nums[1] = 1。左半边上界 min(0, 1) = 0，递归 dfs(0, 0)：mid = 0，nums[0] = 1；左半边上界 min(-1, 1) = -1 返回 -1；nums[0] == 0？1 != 0；右半边下界 max(1, 1) = 1，dfs(1, 0) 返回 -1；整体 -1。回到 dfs(0, 2)：检查 nums[1] == 1，成立，返回 1。

这个用例说明两点：一是重复元素下算法依然正确；二是"先左后右"确实拿到了最小索引——下标 1 是唯一的魔术索引，但如果先检查 mid 再看左边，在别的数据上就可能先返回一个偏大的答案。

代码实现

class Solution {
    public int findMagicIndex(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }

    private int dfs(int[] nums, int lo, int hi) {
        if (lo > hi) {
            return -1;
        }

        int mid = lo + (hi - lo) / 2;

        int leftHi = Math.min(mid - 1, nums[mid]);
        int leftAns = dfs(nums, lo, leftHi);
        if (leftAns != -1) {
            return leftAns;
        }

        if (nums[mid] == mid) {
            return mid;
        }

        int rightLo = Math.max(mid + 1, nums[mid]);
        return dfs(nums, rightLo, hi);
    }
}

func findMagicIndex(nums []int) int {
    return dfs(nums, 0, len(nums)-1)
}

func dfs(nums []int, lo, hi int) int {
    if lo > hi {
        return -1
    }
    mid := lo + (hi-lo)/2

    leftHi := min(mid-1, nums[mid])
    if answer := dfs(nums, lo, leftHi); answer != -1 {
        return answer
    }
    if nums[mid] == mid {
        return mid
    }

    rightLo := max(mid+1, nums[mid])
    return dfs(nums, rightLo, hi)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

时间复杂度：最坏 $O(n)$。当所有元素相等（如 [1, 1, 1, ..., 1]）时，min/max 的剪枝完全不生效，每层都要同时递归左右两侧，递归树覆盖全部下标。平均情况下剪枝能砍掉大片区间，接近 $O(\log n)$，但没有对数级的最坏保证——这是重复元素带来的本质代价。

空间复杂度：$O(\log n)$ 期望、最坏 $O(n)$，全部来自递归调用栈。剪枝有效时递归深度是对数级；退化时深度与数组长度同阶。

关键点总结

二分成立的前提是单调性，先验证再动手。看到"有序数组"不要条件反射写二分，要先写出判定函数（这里是 f(i) = nums[i] - i）并确认它单调。本题正是因为允许重复而使 f 失去单调性，标准二分直接失效。

单调性不足时，退而求其次用"有序性做剪枝"。有序数组即使不能丢半边，也能给出"某个下标区间不可能有解"的必要条件。把 $[lo, mid-1]$ 收缩成 $[lo, \min(mid-1, nums[mid])]$ 就是这类推理的范式：从"值只会更小、下标只会更小"反推出解的下标上界。

要"最小答案"就把递归顺序排成下标升序。先左、再中、后右，第一个非 -1 结果即是全局最小，可以立刻短路返回，省掉所有比较和后续搜索。反过来若题目要"最大"，把顺序整体镜像即可。

区间收缩必须严格，否则递归不终止。min(mid - 1, ...) 里的 -1 和 max(mid + 1, ...) 里的 +1 保证了子区间一定不含 mid、规模严格变小，是防爆栈的机械保障。

面试视角：主动区分"严格递增"和"允许重复"两个版本。面试官很可能先问"如果元素互不相同呢"——那时 f 严格单调，标准二分 $O(\log n)$；再放宽到允许重复，就必须改成本题的剪枝递归，并诚实说明最坏 $O(n)$。能把"为什么退化"讲清楚（举出全相等数组这个反例），比写出代码更能证明你真的理解二分的前提。

易错点总结

错误写法：按标准二分写成 if (nums[mid] < mid) lo = mid + 1; else hi = mid - 1; → 用例 nums = [-10, -5, 2, 2, 2, 3, 4, 7, 9, 12]：mid = 4 时 nums[4] = 2 < 4，直接丢掉左半边，但答案 2 恰在左半边（nums[2] = 2），返回 -1，正确答案是 2。

错误写法：先检查 nums[mid] == mid 再递归左半边 → 用例 nums = [0, 1, 2]：mid = 1 时先命中 nums[1] == 1 返回 1，但下标 0 也是魔术索引且更小，正确答案是 0。要最小答案就必须先搜左边。

错误写法：左递归的上界写成 mid - 1（不做 min 剪枝） → 用例 nums = [1, 1, 1, ..., 1]：答案仍然正确，但剪枝失效，所有情况都退化成完整的 $O(n)$ 递归；更糟的是丢掉了本题的核心考点，面试里等同于交白卷。

错误写法：左递归上界写成 min(mid, nums[mid])（漏了 -1） → 用例 nums = [5, 5, 5]：dfs(0, 2) 中 mid = 1，左递归变成 dfs(0, 1)，其内部 mid 又可能是 1，子区间没有严格收缩，无限递归直到 StackOverflowError。

错误写法：右递归下界写成 min(mid + 1, nums[mid])（该用 max 却用了 min） → 用例 nums = [-5, -3, 2]：mid = 1 时 nums[1] = -3，右递归下界变成 min(2, -3) = -3，区间 [-3, 2] 里的负下标被访问，数组越界抛异常。

错误写法：leftAns != -1 写成 leftAns > 0 → 用例 nums = [0, 2, 3]：左边找到答案 0，但 0 > 0 不成立被当作"无解"，继续往下走最终返回 -1，正确答案是 0。0 是完全合法的魔术索引，判定必须用 != -1。

错误写法：mid = (lo + hi) / 2 → 本题规模小不会触发，但同类题上 lo + hi 溢出成负数后 mid 变负，数组越界。统一写 lo + (hi - lo) / 2。

错误写法：终止条件写成 if (lo >= hi) return nums[lo] == lo ? lo : -1; → 用例 nums = []：lo = 0、hi = -1，0 >= -1 成立，直接访问 nums[0] 越界。空数组必须由 lo > hi 静默接住。

错误写法：Go 里把两个辅助函数删掉但仍写 min(mid-1, nums[mid])，同时项目跑在 Go 1.20 及以前 → 编译报错 undefined: min。内置的 min/max 是 Go 1.21 才有的，自带一份实现最稳妥。

错误写法：改成迭代版时用一个栈存待搜索区间，但按后进先出的顺序处理 → 用例 nums = [0, 1, 2]：右半边的区间先被弹出处理，先找到下标 2 就返回，正确答案是 0。改迭代必须显式保证下标升序，否则"最小"这个要求就丢了。

错误写法：把返回值定义成"任意一个魔术索引"而在递归里比较大小取 Math.min → 用例 nums = [-1, 0, 2]：无解时子调用返回 -1，Math.min(-1, 2) 得到 -1，把找到的答案 2 覆盖成"无解"。用 -1 当哨兵就不能再用 min 聚合，只能靠"先左后右 + 立即返回"。

相似题目

题目	难度	考察点
面试题 10.05. 稀疏数组搜索	简单	同样是"有序但被破坏"的二分，空串取代重复值成为单调性的杀手
704. 二分查找	简单	单调性完整的标准模板，用来对照本题为什么不能直接丢半边
81. 搜索旋转排序数组 II	中等	重复元素同样让判定失效，处理方式是收缩边界而非本题的区间剪枝
540. 有序数组中的单一元素	中等	靠下标奇偶性重建单调判定，是"造出单调量"的另一种思路
852. 山脉数组的峰顶索引	中等	数组整体无序但相邻差值单调，二分作用在差分而非原值上