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

二分查找实战：两道经典题目解析

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

题目描述

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

解题思路

这道题的核心在于利用二段性。虽然数组整体不是有序的，但旋转后形成的两个子区间各自是有序的。

我们可以将数组分为两部分：

• 左半部分：所有元素都大于等于首元素 nums[0]
• 右半部分：所有元素都小于等于首元素 nums[0]

最小值恰好位于这两部分的交界处。通过比较中间元素 mid 与首元素 nums[0] 的大小关系，可以判断 mid 落在哪个区间，从而收缩搜索范围：

• 若 nums[mid] >= nums[0]，说明 mid 在左半部分，最小值一定在右侧，令 left = mid + 1
• 若 nums[mid] < nums[0]，说明 mid 在右半部分，最小值可能在当前位置或左侧，令 right = mid

当 left == right 时，即找到最小值。

特殊情况处理：如果数组本身没有旋转（即 nums[0] <= nums[n-1]），直接返回首元素即可。

C++ 代码实现

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        // 如果数组未旋转，直接返回第一个元素
        if (nums[0] <= nums[n - 1]) {
            return nums[0];
        }

        int left = 0;
        int 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];
    }
};

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)。关键在于识别数据中的单调性或二段性，并据此设计判断条件来缩小搜索空间。在实际工程中，面对有序数据的检索、极值查找等问题，优先考虑二分法往往能获得更优的性能表现。