LeetCode 面试题 08.03. 魔术索引

约 5 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 程序员面试金典（第 6 版） 腾讯
标签
数组 二分查找

题目描述

✅ 面试题 08.03. 魔术索引

image-20260929105811792

题意分析

在允许重复值的非递减数组中，寻找最小的下标 i，使 nums[i] == i；不存在则返回 -1。即使中点已经满足条件，也不能立即返回，因为左侧可能还有更小的答案。

解法：左优先递归 + 有序剪枝

核心思路

[!blue]
利用数组有序性分别剪掉两侧不可能成为答案的位置。 不能把 nums[i] - i 当成单调函数：遇到重复值时它会下降，数组值跳跃时它又可能上升。因此只凭 nums[mid] 与 mid 的大小关系，无法像普通二分一样直接舍弃完整半区。

取中点 mid，令 v = nums[mid]。对左侧位置 j < mid，有 nums[j] <= v；如果 j > v，就必然 nums[j] < j，不可能相等。所以左侧只需搜索 [lo, min(mid - 1, v)]，其余左侧位置可以排除。

对右侧位置 j > mid，有 nums[j] >= v；如果 j < v，就必然 nums[j] > j，同样不可能相等。因此右侧只需搜索 [max(mid + 1, v), hi]。两个子区间始终排除中点；若 v 为负数或远大于下标范围，使某一侧成为空区间，就由递归边界直接返回，不会访问越界下标。

搜索顺序固定为左侧、中点、右侧。先让左递归返回其中最小的答案；若没有，再检查中点，最后才搜索右侧。剪掉的位置已经证明无解，所有未剪掉的较小下标又先于较大下标处理，因此第一次找到的就是全局最小下标。

最坏情况下两侧都要搜索，时间仍可能为线性；但两侧区间互不重叠，且每个子区间都不超过原区间的一半，所以每个位置最多成为一次中点，递归深度保持对数级。

解题步骤

  1. 空区间返回 -1。
  2. 取中点，先搜索剪枝后的左侧区间。
  3. 左递归结果不为 -1 就直接返回；否则检查 nums[mid] == mid，成立则返回 mid。
  4. 左侧和中点都无解时，再搜索剪枝后的右侧区间。下标 0 也是有效答案，判断是否找到时必须与 -1 比较。

代码实现

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)$。剪枝可能无法继续缩小两侧范围，但子区间互不重叠，每个位置至多检查一次。
  • 空间复杂度：$O(\log(n+1))$，每个子区间至多为原区间一半。

关键点总结

[!green]

  • 重复值使普通二分的单调判定失效。
  • 范围剪枝来自数组值的有序性。
  • 先左后中再右，保证首次返回的下标最小。

易错点总结

[!yellow]

  • nums[mid]<mid 就只搜右侧：重复值条件下左侧仍可能有解。
  • 先命中中点就返回：左侧可能仍有更小的合法下标。
  • 子区间仍包含 mid：可能无法收缩。
  • 把答案零当作失败：成功条件应为不等于 -1。

相似题目

题目 难度 关联与区别
1064. 不动点 简单 严格递增数组使nums[i]-i非递减；本题允许重复后失去这个单调性，不能按中点符号直接舍弃半区。
34. 在排序数组中查找元素的第一个和最后一个位置 中等 两题都要求最早位置，搜索中命中一个候选后仍要保留更左结果的可能。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/12797170
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！