剑指 Offer 53 - II. 0～n-1中缺失的数字

剑指 Offer 53 - II. 0～n-1中缺失的数字

• 解题思路
• 代码

解题思路

有序数组，二分搜索，注意虽然数字缺失，但是下标完整。
比如0 1 2 4，对应的下标为0 1 2 3，这样可以根据下标和数字是否对应来判断缺失的区域在左边还是右边。
然后就是返回值：

代码

class Solution {
    public int missingNumber(int[] nums) {
        int left=0;
        int right=nums.length-1;

        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==mid){//下标完整，缺失部分在右边
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
         //终止条件是l = r + 1, 因此最终r在左，l在右，而切割线右边的l即为左边界
        return left;
    }
}