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

变体：以左端点为参照

有时也可以比较 nums[mid] 和 nums[0]。如果 nums[mid] >= nums[0]，说明 mid 在左半段，最大值在 mid 或其右侧，最小值则在 mid+1 之后。注意处理数组未旋转的情况。

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

题目背景

一个长度为 n-1 的递增排序数组中的所有数字都在 0~n-1 范围内且无重复，请找出其中缺失的那个数字。

核心思路

这道题最直观的方法是求和公式或哈希表，但我们可以利用索引与值的对应关系进行二分优化。

在缺失数字出现之前，数组满足 nums[i] == i；一旦缺失数字出现，后续所有元素都会发生偏移，即 nums[i] != i。 这种性质构成了典型的二段性：

• 左半段：nums[i] == i
• 右半段：nums[i] != i

判断逻辑： 取中点 mid：

1. 若 mid == records[mid]，说明缺失位置在右侧，left = mid + 1。
2. 若 mid != records[mid]，说明缺失位置在左侧或即为当前位置，right = mid。 循环结束时，left 指向第一个不匹配的位置，即为缺失数字。

代码实现

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

总结

这两个问题展示了二分查找的灵活性。核心不在于死记硬背模板，而在于识别数据中的单调性或分段特性。无论是旋转数组的分界点，还是缺失数字导致的索引偏移，只要找到合适的判断条件，就能将线性搜索优化为对数级效率。在实际面试中，这类变体非常常见，建议多动手推导边界情况。