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

C++ 算法代码（以 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 中缺失的数字

题目链接

LCR 173. 点名 - 力扣（LeetCode）

题目描述

题目示例

解法（二分查找）

算法思路

关于这道题中，时间复杂度为 O(N) 的解法有很多种，而且也都比较好想到，这里就不再赘述。本题我们主要介绍的是一个时间复杂度为 O(logN) 的最优解法二分法：

在这个升序的数组中，我们发现：

• 在第一个缺失位置的左边，数组内元素都是与数组下标相等的；
• 在第一个缺失位置的右边，数组内的元素都是与数组下标不相等的。

因此，我们可以利用这个【二段性】，来使用【二分查找】算法。

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

算法总结及流程解析