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

代码实现（以 nums[0] 为参照物）

class Solution {
public:
    int findMin(vector<int>& nums) {
        // 选择 nums[0] 作为参照物
        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 与 right 相遇的位置是数组最大值
        // left+1 位置则是最小值（数组不是一直递增的情况）
        if(left == nums.size() - 1) {
            // 特殊情况：旋转到数组一直递增
            return nums[0];
        }
        return nums[left + 1];
    }
};

流程解析

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

题目描述

给定一个包含 0 到 n 中 n 个数的数组，找出其中缺失的那个数。

题目示例

输入：[0,1,3]
输出：2

输入：[0,1,2,3,4,5,6,7,9]
输出：8

解法（二分查找）

思路解析

虽然线性扫描也能解决，但利用数组有序的特性，我们可以用二分查找将时间复杂度优化至 O(logN)。 在这个升序数组中，存在明显的二段性：

• 在第一个缺失位置的左边，数组内元素都是与数组下标相等的；
• 在第一个缺失位置的右边，数组内的元素都是与数组下标不相等的（因为前面的数缺了一个，后面的数都会比下标大 1）。

因此，我们可以利用这个特性来定位首个不匹配的位置。

代码实现

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;
            }
        }
        // 如果 left 位置的值等于下标，说明缺失的是下一个数
        if(left == records[left]) {
            return records[left] + 1;
        }
        // 否则 left 位置就是第一个不匹配的位置，缺失的就是它本身
        return records[left] - 1;
    }
};

流程解析