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

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

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，[0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]。请找出其中最小的元素。

解题核心

这道题的关键在于利用数组的'二段性'。虽然整体不是有序的，但我们可以观察到：

1. 如果我们将数组分为两部分，一部分是严格递增的，另一部分也是严格递增的（只是数值较小）。
2. 最小值一定位于那个'断点'处。
3. 通过比较中间值 mid 和右端点 right 的值，我们可以判断 mid 落在哪一段。

具体逻辑：

• 若 nums[mid] > nums[right]，说明最小值在 mid 右侧（因为 mid 处于较大的前半段），此时 left = mid + 1。
• 若 nums[mid] <= nums[right]，说明最小值在 mid 左侧或就是 mid 本身（mid 处于较小的后半段），此时 right = mid。

当 left == right 时，循环结束，该位置即为最小值。

C++ 参考实现

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 以右端点为基准进行比较
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
};

注意：这里选择 nums[right] 作为参照物比 nums[0] 更稳健，避免了处理数组完全有序时的特殊分支判断，代码更简洁。

---

24. 0~n-1 中缺失的数字

题目描述

一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0～n-1 之内。在范围 0～n-1 内的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。

解题核心

这道题同样可以利用二分查找将时间复杂度优化到 O(logN)。观察数组下标与数值的对应关系：

• 在缺失数字出现之前，所有元素都满足 nums[i] == i。
• 在缺失数字出现之后，由于前面的数字少了一个，后续元素都会发生偏移，满足 nums[i] != i。

这种'前真后假'的特性构成了典型的二段性，非常适合二分查找。

具体逻辑：

• 计算中间索引 mid。
• 若 nums[mid] == mid，说明缺失的数字在右侧，left = mid + 1。
• 若 nums[mid] != mid，说明缺失的数字在左侧（包含 mid），right = mid。

循环结束后，left 指向第一个不满足 nums[i] == i 的位置，即缺失的数字。

C++ 参考实现

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int left = 0;
        int right = records.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (records[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // 循环结束时 left 指向第一个不匹配的位置
        // 如果整个数组都匹配（理论上不会发生，除非数据异常），则返回 n
        return left;
    }
};

总结

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

1. 旋转数组：通过比较中间值与边界值来判断单调区间，从而收缩搜索范围。
2. 缺失数字：利用索引与数值的等差关系构建二段性，定位断点。

掌握这些模式后，遇到类似的'局部有序'或'索引偏移'问题，就能迅速联想到二分查找的解法。