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

题目给定一个原本升序排序且元素互不相同的数组，经过旋转后，要求找到最小值。暴力遍历时间复杂度为 O(N)，题目要求使用 O(log N) 算法，即典型二分查找。

算法原理

二分查找的核心在于判断是否存在二段性。初始数组有序，旋转后可分为两段递增序列：

目标是最小值点 C。若 mid 的值大于 D（右半段末尾），说明 mid 在 AB 段，最小值在右侧，令 left = mid + 1；若 mid 的值小于 D，说明可能命中答案或位于 CD 段，令 right = mid。

若参照物选择 A（首元素），需单独考虑数组未旋转的情况。

算法编写

参照物为 D 的情况：

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

参照物为 A 的情况：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        int x = nums.size() - 1;
        if(nums[0] < nums[x]) 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];
    }
};

若参照物为 A，当数组连续递增（如 [1,2,3,4]）时，任意数均大于 A，left 会一直增加至最大值，此时需单独判断并返回 nums[0]。

寻找缺失的数字

题目解析

题目要求返回缺失的那个数字。常见解法包括遍历（O(N)）、等差求和公式（O(N)）、位运算异或（O(N)）及哈希映射（O(N) 空间）。上述方法效率较低，可利用二分查找优化。

算法原理

核心在于寻找二段性：缺失数字左侧，数组元素等于下标；缺失数字右侧，数组元素不等于下标。目标值为右侧区间的左端点，因此 left = mid + 1，right = mid。

算法编写

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 与 nums[left] 相等，故返回 left + 1。

--- 参考题目 --- 162. 寻找峰值 - 力扣（LeetCode） 153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode） LCR 173. 点名 - 力扣（LeetCode）