0～n-1中缺失的数字

题目：

一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0 ～ n-1 之内。在范围 0 ～ n-1 内的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。

输入: [0,1,3]
输出: 2

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

思考：

提示

• 排序数组中的搜索问题，首先想到 二分法

• 可以想象将数组分成两部分：左边索引和对应值相等，右边索引和对应值不相等

• 即将题目转化为 寻找右边数组的第一个元素

题解：

class Solution {
    public int missingNumber(int[] nums) {
        int i = 0,j = nums.length-1;
        while ( i<= j){
            int mid = (i + j)/2;
            if (nums[mid] == mid) i = mid + 1;
            else j = mid - 1;
        }
        return i;
    }
}