二分查找实战：旋转排序数组最小值与点名问题

24. 点名

题目描述

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于递增数组 records。若某位同学缺席，其学号即为缺失的数字。请返回缺席同学的学号。

算法思路

这是一个典型的利用索引与数值对应关系进行二分的场景。在有序数组中，如果没有缺失数字，那么 nums[i] == i。一旦出现了缺失数字，缺失位置之后的所有元素都会发生偏移，导致 nums[i] > i。

这构成了明显的二段性：

• 缺失位置左侧：nums[i] == i
• 缺失位置右侧：nums[i] != i（实际上是 nums[i] > i）

我们只需要找到第一个满足 nums[i] != i 的位置，那个位置就是缺失的数字。如果遍历完都没有发现不匹配，说明缺失的是最后一个数字 n。

C++ 代码实现

class Solution {
public:
    int takeAttendance(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == mid) {
                // 左边正常，缺失在右边
                left = mid + 1;
            } else {
                // 左边异常，缺失在左边（含 mid）
                right = mid;
            }
        }
        
        // 判断最终位置是否匹配
        if (nums[left] == left) {
            return left + 1;
        }
        return left;
    }
};

总结

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

1. 旋转数组：通过比较中点与基准值（如首元素）来确定搜索方向，关键在于识别'断点'。
2. 缺失数字：利用索引与值的单调关系，定位第一个不满足等式的位置。

掌握这种'二段性'思维，能帮助你快速构建二分逻辑，将时间复杂度优化至 O(log n)。