二分查找实战：旋转数组最小值与缺失数字

题目描述

一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0～n-1 之内。在范围 0～n-1 内的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。

解题核心

这道题同样可以利用二分查找将时间复杂度优化到 O(logN)。观察数组下标与数值的对应关系：

• 在缺失数字出现之前，所有元素都满足 nums[i] == i。
• 在缺失数字出现之后，由于前面的数字少了一个，后续元素都会发生偏移，满足 nums[i] != i。

这种'前真后假'的特性构成了典型的二段性，非常适合二分查找。

具体逻辑：

• 计算中间索引 mid。
• 若 nums[mid] == mid，说明缺失的数字在右侧，left = mid + 1。
• 若 nums[mid] != mid，说明缺失的数字在左侧（包含 mid），right = mid。

循环结束后，left 指向第一个不满足 nums[i] == i 的位置，即缺失的数字。

C++ 参考实现

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int left = 0;
        int right = records.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (records[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // 循环结束时 left 指向第一个不匹配的位置
        // 如果整个数组都匹配（理论上不会发生，除非数据异常），则返回 n
        return left;
    }
};

总结

这两道题展示了二分查找在不同场景下的变体应用：

1. 旋转数组：通过比较中间值与边界值来判断单调区间，从而收缩搜索范围。
2. 缺失数字：利用索引与数值的等差关系构建二段性，定位断点。

掌握这些模式后，遇到类似的'局部有序'或'索引偏移'问题，就能迅速联想到二分查找的解法。