题目描述
一个长度为 n−1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0 到 n−1 之内。
在范围 0 到 n−1 的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。
数据范围
1≤n≤1000
样例
输入：[0,1,2,4] 输出：3
方法一：二分法 O(logn)
观察题目，可以在缺失元素前面的所有元素下标和数值都是相等的，而从该分界线往后则是数值比下标大 1 。
所以，我们可以通过二分法来找到第一个下标与数值不想等的位置，该下标就是 0~n-1 缺失的数字，这其实相等于去求一个数值与下标不相等的左边界。
特殊情况： 当所有数都满足 nums[i] == i 即数组中所有元素的数值都等于其对应的下标时，缺失的元素就是 n 。
class Solution { public: int getMissingNumber(vector<int>& nums) { if (nums.empty()) return 0; int l = 0, r = nums.size() - 1; while (l < r) { int mid = l + r >> 1; if (nums[mid] != mid) r = mid; else l = mid + 1; } if (nums[r] == r) r++; return r; } };
欢迎大家在评论区交流~
