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

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]) {
                // 中点在左半段，最大值在 mid 或右侧
                left = mid;
            } else {
                // 中点在右半段，最大值在 mid 左侧
                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(logN)。

关键在于发现数组元素的索引与数值的关系：

• 在缺失数字出现之前，所有元素都满足 nums[i] == i；
• 在缺失数字出现之后，由于前面少了一个数，后续所有元素都会比索引大 1，即 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 {
                // 否则缺失数字在左侧或就是当前位置
                right = mid;
            }
        }
        
        // 根据边界情况返回结果
        if (left == records[left]) {
            return records[left] + 1;
        }
        return records[left] - 1;
    }
};

流程解析

总结

这两道题都是二分查找的经典变体。第一题利用了旋转数组的分段单调性，通过比较中点与边界值来锁定最小值区间；第二题则利用了索引与值的对应关系，寻找性质发生突变的分界点。在实际编码中，务必注意循环终止条件以及边界情况的特殊处理，比如数组未旋转或单元素的情况，这样才能保证算法的鲁棒性。