剑指 Offer 53 - II. 0～n-1 中缺失的数字

频次 ★★★ · 难度 🟢 · 高频：美团

题目

长度为 n-1 的递增排序数组，包含 0~n-1 中的 n-1 个数，找出缺失的那个。

示例：

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

输入: [0,1,2]
输出: 3

思路

二分查找”第一个下标与值不等的元素”。

有序数组 [0,1,2,...,n-1] 缺失一个数后，会出现一个分界点：分界点之前的元素值 == 下标，之后的元素值 > 下标（值 = 下标 + 1）。找到第一个 nums[i] != i 的位置即可。

• nums[mid] == mid → 缺失在右半，l = mid + 1
• nums[mid] != mid → 缺失在左半（含 mid），r = mid

结束时 l == r 即为缺失值。

代码

public int missingNumber(int[] nums) {
    int l = 0, r = nums.length;               // r = n（因为缺失值可能= n）
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == mid)
            l = mid + 1;                      // 左侧正常，缺失在右侧
        else
            r = mid;                          // 有问题，在左侧找
    }
    return l;                                 // l 就是缺失的数字
}

复杂度

• 时间：O(log n)
• 空间：O(1)

边界条件

• 缺失 0（[1,2,3]）：首个元素 nums[0]=1 != 0，mid=0 时 nums[0] != 0，r 左移 → 找到 0 ✅
• 缺失 n（[0,1,2]，缺失 3）：所有 nums[i] == i，二分结束 l r n，返回 3 ✅
• 长度 1：r = 1，mid = 0，比较 nums[0] == 0？ 是则 l=1 返回 1；否则 r=0 返回 0

变式

• 缺失多个数不能一次二分，需遍历
• [0,1,2,4,5]（非连续但缺失一个）：本题条件是完整连续 0~n-1，只缺一个；非连续场景需其他方法

易错点

• r 初始化为 n 而非 n-1：因为缺失的数字可能是 n（数组末尾之后），此时需要返回 n
• 循环条件 l < r，结束时 l == r 就是缺失值——不需要后处理判等
• 用 nums[mid] 与 mid 比较，不是 mid 与 nums[mid] 比——前者反应”值与下标对齐”这个性质
• 剑指 53 有两个子题：I 是统计 target 在排序数组出现次数（二分边界），II 才是本题缺失数字

面试追问

• 为什么 O(log n) 而不是遍历 O(n)？ 答出”有序”就想到二分。条件反射：看到有序 + 查找 → 二分
• 缺失值在数组末尾时怎么处理？ r 初值设为 n，数组全部对齐时 l 推进到 n → 返回 n。这是二分边界设计中最巧妙的一点，面试中主动点出

关联题

• 同套路：34. 在排序数组中查找元素的第一个和最后一个位置 —— “找第一个满足/不满足条件的位置”的边界二分
• 进阶：剑指 Offer 53 - I. 在排序数组中查找数字 I —— 统计次数，用两次二分找边界
• 知识点：二分查找左边界/右边界/缺失值模板对比