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

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

题目描述

给定一个升序排列的数组，该数组在某个未知的下标处进行了旋转。例如 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]。请找出其中最小的元素。

解题思路

这道题的关键在于利用数组的局部有序性。虽然整体不单调，但旋转点将数组分成了两个递增的子序列。我们可以通过比较中间元素 mid 与边界元素的关系，判断最小值位于哪一侧。

方案一：以末尾元素为基准

我们将 nums[n-1] 作为参照物。如果 nums[mid] > nums[n-1]，说明 mid 落在第一个递增区间（较大的那部分），最小值一定在右侧；反之，最小值可能在左侧或就是 mid 本身。

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[nums.size() - 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
};

方案二：以开头元素为基准

另一种思路是拿 nums[0] 做对比。如果 nums[mid] >= nums[0]，说明 mid 还在前半段（较大值区域），需要向右收缩；否则向左收缩。注意处理数组未旋转的特殊情况。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] >= nums[0]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        // 循环结束 left 指向最大值位置，最小值在其后一位
        if(left == nums.size() - 1) {
            return nums[0];
        }
        return nums[left + 1];
    }
};

---

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

题目描述

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

解题思路

暴力遍历的时间复杂度是 O(n)，但我们可以利用索引与数值的对应关系将其优化到 O(log n)。在未缺失数字的情况下，数组下标 i 对应的值应该等于 i。一旦遇到缺失数字，后续所有元素的值都会比下标大 1。这种'相等'与'不相等'的分界点，正是二分查找的目标。

核心逻辑

• 若 records[mid] == mid，说明左半部分完整，缺失值在右侧。
• 若 records[mid] != mid，说明缺失值已在左侧或当前位置。

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(mid >= records[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // 判断最后位置是否匹配
        if(left == records[left]) {
            return records[left] + 1;
        }
        return records[left] - 1;
    }
};

通过上述两个案例可以看出，二分查找不仅仅是用于查找特定值，更常用于根据某种性质划分区间。掌握这种二段性的构建方法，能解决很多看似复杂的变体问题。