题目链接

题意

长度为n-1的递增数组，其中每次数字都是0~n范围内。找出缺失的数字。

题解

这题也是自然想到二分，但是怎么去二分，二分的判断条件是什么要思考一下。
观察数组，我们会发现，数组由这样的两个部分组成：

  • nums[i]=i
  • nums[i]剑指Offer 53-II. 0~n-1中缺失的数字 - 图1i

那么这两部分的中间那个下标就是我们要找的数。
自然，二分条件也就出来了。

代码

  1. class Solution {
  2. public:
  3.     int missingNumber(vector<int>& nums) {
  4.         int l = 0, r = nums.size()-1;
  5.         int mid;
  6.         while (l <= r) {
  7.             mid = (l + r) / 2;
  8.             if (nums[mid] == mid) l = mid + 1;
  9.             else r = mid - 1;
  10.         }
  11.         return l;
  12.     }
  13. };