题目
一个长度为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
解题
方法一：二分查找
写法一：
比如例子[0,1,2,3,5,6]
left会经过[0,1,2,3]连续区间，停止到值为5的地方，right也会停到值为5的地方。
但是left索引就是本该缺失的值4。
但是这种写法，相比写法二，只能查找缺失值非首尾的，数。
这种写法，要查找首位缺失，就要在开始，单独判断。
class Solution { public: int missingNumber(vector<int>& nums) { if(nums[right]==right) return right+1; if(nums[left]==1) return 0; int left=0,right=nums.size()-1; while(left<right){ int mid=(left+right)/2; if(nums[mid]==mid){ left=mid+1; } else right=mid; } return left; } };
写法二：
例子[0,1,3]
比如left=2 （指向3），right=1的时候循环中断
left索引就是缺少的数，原来本该是2，却指向了3。
class Solution { public: int missingNumber(vector<int>& nums) { int left=0,right=nums.size()-1; while(left<=right){ int mid=(left+right)/2; if(nums[mid]==mid) left=mid+1; else right=mid-1; } return left; } };
