用C++讲讲二分查找找缺失元素的最佳思路

以最常见的一种为例：数组 nums 长度为 n，本应是从 nums[0] 开始的连续整数，即理论上 nums[i] 应该等于 nums[0] + i。如果没有缺失，任意位置都满足这个等式；一旦某个位置开始出现 nums[i] > nums[0] + i，说明缺失的元素出现在这个位置之前（或就是这个位置）。于是可以二分：每次看 mid 位置是否还满足 nums[mid] == nums[0] + mid，满足说明缺的数在右半边，不满足说明缺的数在左半边或就是当前位置，收缩区间直到定位到第一个不满足等式的位置。

class Solution {
public:
    int findMissing(vector<int>& nums) {
        int left = 0, right = (int)nums.size() - 1;
        int base = nums[0]; // 理论上第 0 位应该是的值

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == base + mid) {
                // 左半边完好，缺失点在右边
                left = mid + 1;
            } else {
                // 当前位置已经错位，缺失点在这里或更左边
                right = mid;
            }
        }

        // 循环结束时 left == right，指向第一个错位的位置
        return base + left;
    }
};

这个写法的关键在于二分的判断条件不是直接比较 nums[mid] 和目标值，而是比较「实际值」和「期望值」的关系，这是数组类二分和普通查找类二分最大的区别：普通二分是在数值空间里找目标，这里是在下标空间里通过一个单调的谓词（错位与否）来收缩边界，本质上是二分查找里「找第一个满足某条件的位置」这一类模板的应用。

复杂度上时间是 O(log n)，空间 O(1)，比遍历一遍数组做差值判断（O(n)）或者用求和/异或的方法（同样 O(n)，虽然更省心但没利用上数组有序这个条件）要快。

几个需要注意的边界情况：如果缺失的元素正好是数组末尾之后那个数（比如 1 到 n+1 缺了 n+1），上面这个写法最终 left 会等于 nums.size()-1 但 nums[left] 仍然等于 base+left（因为数组里没有错位点），这时候要在循环外单独判断，返回 nums[right] + 1 或者 base + nums.size()，具体写法要看题目里数组的范围定义是左闭右开还是左闭右闭，写代码前一定要先把「缺失可能发生在数组末尾之后」这个边界情况想清楚，否则容易漏掉这一种情况导致返回错误答案。

如果数组不是从固定 base 开始，而是像 1 到 n 少一个数变成长度 n-1 的场景，判断条件要相应改成 nums[mid] – mid 是否等于某个不变量（比如恰好等 1），原理是一样的，只是期望值的表达式不同。