二分搜索

注意要点

1. 确定搜索的范围和区间，通常称为上边界和下边界（左右边界）
2. 取中间数判断是否符合条件
3. 不满足该往哪个半边靠近

4. 
   

   leetcode

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

   var missingNumber = function(nums) {
    let left = 0,
        right = nums.length - 1;
          //上边界和下边界
    while (left <= right) {
        let mid = Math.floor((left + right) / 2); //nums[mid]为中间数
        if (mid === nums[mid]) {
            left = mid + 1;
        } else if (mid < nums[mid]) {
            right = mid - 1;
        }
    }
    return left;
   };