这个题当然可以用遍历的方法，但是我们只要看到递增排序数组，就应该想到用二分法去做。但是这个题跟其它的二分法不是很一样，它没有明确要查找的target 或者左边界，右边界等，而是数组的中间有一个断点。我们可以根据这个断点把数组分为两部分：左数组和右数组，然后我们可以发现，左数组的所有元素的值都和他们的索引相同，而右数组则不是。

　　因此，我们可以用 值是否与索引相同这一点来判断是左数组还是右数组。而根据题目要求，我们需要返回右数组的第一个元素的索引，它就是缺失的元素。

   　那么，我们使用二分查找，最终 left 应该对应的 右数组的第一个元素，而 right 应该对应左数组的最后一个元素，即 left == right + 1时退出。

class Solution {
    public int missingNumber(int[] nums) {
        //尝试二分法
        int left = 0,right = nums.length-1,mid;
        //可以跟索引进行对应
        while(left<=right){ //当 left == right+1 时退出
            mid = left + (right - left)/2;
            if(nums[mid]==mid){
                //mid在左数组，右数组第一个元素在[mid+1,right]上
                left = mid + 1;
            }else{
                //mid在右数组，左数组的最后一个元素在[left,mid-1]上
                right = mid - 1;
            }
            //不存在 nums[mid]>mid的情况
        }
        return left; //left对应 右数组的第一个元素
    }
}