一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:
输入: [0,1,3]
输出: 2
示例 2:输入: [0,1,2,3,4,5,6,7,9]
输出: 8
限制：
1 <= 数组长度 <= 10000
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/que-shi-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
对于这道题而言，我们首先可以采用下面这种方法，就是遍历一遍容器，如果容器当前位置的存储的元素和其下标不符合的时候就返回该元素的位置。
class Solution {
public:
int missingNumber(vector<int>& nums) {
int i=0;
for(i=0;i<nums.size();i++)
{
if(nums[i]!=i)
{
return i;
}
}
return i;
}
};
但是上面这种算法的速度比较慢，我们同样可以试试看异或运算。
由于0到n-1的数据应该都是要存在在容器中的，所以我们将容器中的所有数据都进行异或操作^，然后再将这个异或之后的结果跟0到n-1的全部数据都进行异或。
因为两个相同的数字进行异或操作的话就会抵消掉。最终就会剩下那个缺失的数字，也就是我们的结果。
class Solution {
public:
int missingNumber(vector<int>& nums) {
int result=0;
for(auto &num:nums)
{
result ^=num;
}
for(int i=0;i<=nums.size();i++)
{
result^=i;
}
return result;
}
};或者采用二分法的操作
0
1
2
3
0
1
3
4
假设我们上面的是一个缺失了2的数组
left=0,right=3,mid=(left+right)/2=1
但是这个时候1位置对应的数据刚好是1，也就是说1位置以及1左边的全部元素都是没有空缺的，所以我们将我们的查找范围限定到我们的右半区域。
left=mid+1=2
left=2,right=3,mid=(left+right)/2=2
但是我们发现2位置对应的数据并不是2，所以这里我们可以判断产生数据缺失的位置是在2或2的左边的区域，所以我们将我们查找的范围限定在左半区域
right=mid-1=1
这时候left=2,right=1,不满足我们的循环条件，只能跳出，所以我们将我们left的指向的索引返回，也就是2。
注意这里我们只能是返回left，如果返回right的话就会得到比正确结果小1的数据。
为什么会产生这种情况？按照我们上面的判断，第一次二分的时候，我们的0和1对应的数据其实已经检查过都是符合要求的，而我们最终的right返回的数据恰好就是在左边已经检查过的符合要求的数据的最后一位，而我们的left刚好就是缺失的位置。（所以从left<=right的判断条件跳出的话，我们的right始终都是比正确的结果小1）
class Solution {
public:
int missingNumber(vector<int>& nums) {
//定义我们的左右边界
int left=0;
int right=nums.size()-1;
//当我们的左边界小于等于右边界的时候进入循环
while(left<=right)
{
//定义我们中间位置元素的下标
int middle=(left+right)/2;
//如果我们中间位置元素的下标正好等于中间位置对应的元素，就说明
//其中间位置的元素的左边都是没有缺失数据的
//所以我们将我们的搜索范围限定到我们的右边
if(nums[middle]==middle)
{
left=middle+1;
}
else
{
right=middle-1;
}
}
//这里只能返回left
return left;
}
};