day99(9.9)

1. 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

思路：

• 使用二分查找判断中间索引对应数组中的值是否等于索引值
• 如果相等说明错误点在右边，否则在左边

• 分别情况进行右边探索和左边探索（进行递归，改变左右索引值（mid+-1）即可）

  class Solution {
    public int missingNumber(int[] nums) {
        // 二分查找，查看中间值是否等于应该对应索引值
        // 如果不等于对应索引值，那么这个目标值在中间值左边，否则在中间值右边
  
        if(nums[nums.length-1]==nums.length-1){
            return nums[nums.length-1]+1;
        }
        return binarySearch(0,nums.length-1,nums);
  
    }
  
    // 改进的符合该题目的二分查找算法
    private int binarySearch(int left,int right,int[] nums){
        if(left>=right){
            if(nums[left]==left){
                return left+1;
            }
            return left;
        }
        int mid = (left + right)/2;
        int midVal = nums[mid];
        if(mid==midVal){ // 向右边探索
            return binarySearch(mid+1,right,nums);
        }else{
            return binarySearch(left,mid-1,nums);
        }
    }
  }