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

方案二：以左端点为参照

这种写法逻辑略有不同，通过比较中点与首元素来判断 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 中缺失的数字

题目链接

LCR 173. 点名 - 力扣（LeetCode）

题目描述

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

题目示例

解题思路

暴力解法遍历需要 O(N)，但既然数组是有序的，我们可以利用索引与值的对应关系将复杂度降至 O(logN)。

• 在缺失数字出现之前，所有元素的值都等于其索引（nums[i] == i）。
• 在缺失数字出现之后，由于前面少了一个数，后续元素的值都会比索引大 1（nums[i] != i）。

这构成了典型的二段性：左边满足 nums[i] == i，右边满足 nums[i] != i。我们只需找到第一个不满足 nums[i] == i 的位置即可。

代码实现

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;
    }
};

流程解析

总结

这两道题展示了二分查找在不同场景下的变体应用。第一题通过比较数值大小定位断点，第二题通过比较索引与数值的关系定位异常点。掌握这种'二段性'思维，能帮助你快速识别适合二分优化的问题。