0～n-1中缺失的数字

问题描述

一个长度为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

问题分析

刚刚看到这个题目的时候比较的懵逼，不知道如何下手，我们可以逐步的分解来理解题目的意思。假设n的大小分别为3， 5，7，那么对应的长度就是2，4，6。对于n个数字来说肯定有n个大小的数组来表示，但是这个时候只用n-1个大小的数组，必然存在0～n中有一个数字没有地方放置。那么对应的事例就有如下的case：

对于缺省的某个值肯定从该位置就会出现array[i] != i的情况，那么该数字就分为了两个子数组，左边的数据都是符合array[i] = i，右边的数组都是arry[i] != i的情况。那么找到这个右边数组的第一个位置就是我们需要寻找的答案。
左边界和右边界我们定义为i 与j，采用二分查找的方式中间位置定义为m，那么
1.如果array[m] = m， 那么交汇的位置应该在大于m位置，i=m+1；
2.如果array[m] != m, 那么交汇的位置就在小于m的位置，j=m-1；
最后返回我们应该返回相等位置的下一个位置，表示交汇的地点（i的位置）

代码实现

class Solution {
    public int missingNumber(int[] nums) {
        if(nums == null || nums.length == 0){
            return Integer.MAX_VALUE;
        }
        int low = 0;
        int high = nums.length -1;
        int mid = 0;
        //这里有一个等于的判断是放置数组只有一个变量的时候也需要走进去判定
        while(low <= high){
            mid = (low + high) >>> 1;
            if(nums[mid] == mid){
                low = mid + 1;
            }else{
                high = mid -1;
            }
        }
        return low;
    }
}