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

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

二分查找不仅仅是简单的折半搜索，关键在于找到合适的判断标准，将查找区间一分为二。下面通过两道经典题目，深入剖析二分法在不同场景下的应用逻辑。

23. 寻找旋转排序数组中的最小值

题目描述： 已知一个长度为 n 的升序排列数组，在某个未知的下标 k 处进行了旋转（例如 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]）。请找出其中最小的元素。

解题思路

旋转后的数组可以看作由两个有序部分组成。虽然整体无序，但局部依然保留了单调性。我们可以利用这种特性来缩小搜索范围。

核心在于比较中间元素 mid 与边界值的关系：

• 如果 nums[mid] >= nums[0]，说明 mid 位于左半部分（较大值区域），最小值一定在右侧，因此更新 left = mid + 1。
• 如果 nums[mid] < nums[0]，说明 mid 位于右半部分（较小值区域），最小值可能是 mid 或者在左侧，因此更新 right = mid。

当 left == right 时，指针指向的元素即为最小值。此外，若数组本身未发生旋转（即 nums[0] <= nums[n-1]），直接返回首元素即可。

参考实现

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        // 如果数组没有旋转，第一个元素就是最小值
        if (nums[0] <= nums[n - 1]) {
            return nums[0];
        }

        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 中点值大于等于首元素，说明在左半段，最小值在右边
            if (nums[mid] >= nums[0]) {
                left = mid + 1;
            } else {
                // 否则在右半段，最小值在左边或就是 mid
                right = mid;
            }
        }
        return nums[left];
    }
};

24. 点名

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

解题思路

这道题同样可以利用二分查找优化时间复杂度至 O(log n)。观察数组特征可以发现明显的'二段性'：

• 在缺失数字出现之前，数组元素的值与其下标是相等的（nums[i] == i）。
• 从缺失数字开始，后续所有元素的值都会比下标大 1（nums[i] > i）。

基于这个规律，我们比较 nums[mid] 和 mid：

• 若 nums[mid] == mid，说明缺失位置在右侧，令 left = mid + 1。
• 若 nums[mid] != mid（实际为 > mid），说明缺失位置在左侧或就是当前位置，令 right = mid。

循环结束后，left 指向第一个不满足 nums[i] == i 的位置。如果遍历完整个数组都满足条件，则缺失的是最后一个编号 n。

参考实现

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 {
                // 值不等于下标，缺失点在左侧
                right = mid;
            }
        }
        
        // 如果所有位置都匹配，则缺失的是最后一个数
        if (nums[left] == left) {
            return left + 1;
        }
        return left;
    }
};

---

这两道题展示了二分查找的核心思想：不要只盯着'找目标值'，更要关注'如何根据当前状态划分区间'。只要找到那个能让区间一分为二的判断依据，就能高效解决问题。