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

复杂度分析： 时间复杂度 O(log n)，空间复杂度 O(1)。

思考：如果选左端点呢？

尝试以 nums[left] 为基准（A 点）也有类似逻辑，但在数组未旋转（如 [1,2,3,4,5]）时，所有元素都 >= nums[0]，容易导致搜索区间收缩错误。因此，选择右端点作为基准通常更稳健。

二、点名（缺失的数字）

题目描述： 某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于排序数组 records。请返回第一个缺少的学号。

1. 多种解法对比

针对此题，存在多种常见解法，各有优劣：

推荐使用二分查找，因为它能充分利用数组有序的特性，达到对数级效率。

2. 二分查找详解

算法思路

在升序数组中，存在明显的二段性：

1. 缺失位置左侧：元素值等于下标（nums[i] == i）。
2. 缺失位置右侧：元素值不等于下标（nums[i] != i）。

我们可以根据 nums[mid] 与 mid 的关系来收缩区间：

• 若 nums[mid] == mid，说明缺失点在右侧，left = mid + 1。
• 若 nums[mid] != mid，说明缺失点在左侧或当前位置，right = mid。

代码实现

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int left = 0, right = records.size() - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(records[mid] == mid) {
                // 左边连续，去右边找
                left = mid + 1;
            } else {
                // 左边不连续，断点在左边
                right = mid;
            }
        }
        // 处理细节：如果循环结束 left 处仍满足 records[left] == left，则缺失的是最后一个
        return records[left] == left ? left + 1 : left;
    }
};

复杂度分析： 时间复杂度 O(log n)，空间复杂度 O(1)。

3. 总结

这两个问题展示了二分查找在不同场景下的变形应用。核心在于识别出问题的'二段性'，并据此设计正确的区间收缩规则。在实际编码中，务必注意边界条件（如空数组、全匹配等）的处理，确保逻辑闭环。