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

策略二：以 nums[0] 为参照物 此方法寻找的是最大值的位置，最小值在其后一位。需注意处理未旋转的情况。

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 范围内且无重复。请找出其中缺失的那个数字。

算法思路

虽然遍历即可解决，但利用数组有序的特性，我们可以使用二分查找将复杂度降至 O(logN)。

关键性质在于索引与值的对应关系：

• 在缺失位置之前，元素值等于索引值（nums[i] == i）。
• 在缺失位置之后，元素值大于索引值（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 (mid >= records[mid]) {
                // 左半段正常，缺失在右侧
                left = mid + 1;
            } else {
                // 右半段异常，缺失在左侧（含 mid）
                right = mid;
            }
        }
        // 判断边界情况
        if (left == records[left]) {
            return records[left] + 1;
        }
        return records[left] - 1;
    }
};

总结

这两个问题展示了二分查找的核心思想：寻找满足特定条件的临界点。无论是旋转数组的最小值，还是缺失数字的定位，关键在于发现数据分布的单调性或二段性，并据此设计收缩区间的条件。在实际编码中，务必注意 mid 的计算方式以及边界条件的处理，避免死循环或越界。