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

2. 点名

题目描述

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

解题思路

这是一个典型的有序数组查找问题。观察数组特性可以发现明显的二段性：

• 在缺失数字之前，所有元素值等于其下标（nums[i] == i）
• 在缺失数字之后，所有元素值大于其下标（nums[i] > i）

利用这个性质，我们可以通过二分查找定位到第一个满足 nums[i] != i 的位置。该位置即为缺失数字的起始点。

具体逻辑如下：

• 若 nums[mid] == mid，说明缺失数字在右侧，令 left = mid + 1
• 若 nums[mid] != mid，说明缺失数字在左侧或就是当前位置，令 right = mid

循环结束后，left 指向第一个不匹配的位置。需要额外判断一下边界情况：如果遍历完所有元素都没有发现不匹配（即 nums[left] == left），说明缺失的是最后一个数字 n。

C++ 代码实现

class Solution {
public:
    int takeAttendance(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            // 元素值等于下标，缺失数字在右侧
            if (nums[mid] == mid) {
                left = mid + 1;
            } else {
                // 元素值不等于下标，缺失数字在左侧或当前位置
                right = mid;
            }
        }

        // 判断是否所有元素都匹配，若匹配则缺失的是最后一个数
        if (nums[left] == left) {
            return left + 1;
        }
        return left;
    }
};

总结

以上两道题目均利用了二分查找优化时间复杂度至 O(logn)。关键在于识别数据中的单调性或二段性，并据此设计判断条件来缩小搜索空间。在实际工程中，面对有序数据的检索、极值查找等问题，优先考虑二分法往往能获得更优的性能表现。