二分:
左子数组中nums[m] == m
,右子数组中nums[m] != m
,
指针i指向右子数组的首位元素,指针j指向左子数组的末尾元素
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
if (!nums.size()) return 0;
int i = 0, j = nums.size() - 1;
while (i <= j) {
int m = (i + j) >> 1;
if (nums[m] == m) i = m + 1;
else j = m - 1;
}
return i;
}
};