剑指 Offer 53 - II. 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

解答

利用数组的中间元素mid进行二分法判断，如果mid和nums[mid]是相等的，说明mid左边区域的连贯的，缺失的元素在右边区域。

var missingNumber = function(nums) {
    let low = 0, high = nums.length-1
    while(low<=high) {
        let mid=(low+high) >>> 1
        if(mid === nums[mid]) {
            low = mid+1
        } else {
            high = mid-1
        }
    }
    return low
};