二分查找进阶：峰值、旋转数组与缺失数字

暴力遍历是 O(N)，不符合要求。核心在于判断 mid 落在哪一段（递增段还是旋转点后的递减段）。

算法原理

我们将数组分为两段：AB 段和 CD 段。最小值位于 D 点。若 mid 的值小于最后一个元素 nums[x]，说明 mid 在右侧递增段，最小值在左边或就是 mid；若 mid 大于 nums[x]，说明 mid 在左侧递增段，最小值在右边。

代码实现

参照物选择末尾元素：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        int x = nums.size() - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < nums[x]) right = mid;
            else left = mid + 1;
        }
        return nums[left];
    }
};

若参照物选择开头元素 nums[0]，需额外处理未旋转的情况（即整个数组递增）：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        if(nums[0] < nums[right]) return nums[0];
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < nums[0]) right = mid;
            else left = mid + 1;
        }
        return nums[left];
    }
};

寻找缺失的数字

题目背景

在 0 到 n-1 的序列中，有一个数字缺失。

数学求和、哈希等方法虽可行，但空间或时间复杂度不够优。利用下标与值的对应关系可实现 O(log N)。

算法原理

缺失数字之前，元素值等于下标；缺失数字之后，元素值大于下标。这就是二段性。我们要找的是右侧区间的左端点。

代码实现

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int left = 0, right = records.size() - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(records[mid] == mid) left = mid + 1;
            else right = mid;
        }
        return left == records[left] ? left + 1 : left;
    }
};

注意边界情况：若数组完整无缺失（如 0,1,2,3），则缺失的是 4，此时 left 会走到末尾，需特殊判断返回 left + 1。