👐二分查找@

1.二分查找框架

int binarySearch (int[] nums, int target){
    int left = 0;
    int right = ...;
    while (left < right){
        int mid = left + (right - left) / 2;
        if (nums[mid] == target){
            ...
        } else if (nums[mid] < target){
            left = ...
        } else if (nums[mid] > target){
            right = ...
        }
    }
}

分析二分查找的技巧：

1. 不要出现else，而是要把所有情况用else if写清楚，这样可以清晰展现所有细节
2. 计算mid时需要防止溢出。上面代码中left + (right - left) / 2和(left + right)/2 结果相同，但有效防止了left和right太大直接相加导致溢出。

寻找一个数（基本的二分查找）

function binarySearch (nums, target){
    let left = 0
  let right = nums.length - 1 // 注意
  while (left <= right){
      let mid = left + (right - left)/ 2;
    if (nums[mid] === target){
        return mid
    } else if(nums[mid] < target){
        left = mid + 1 // 注意
    }    else if (nums[mid] > target){
        right = mid -1 // 注意
    }
  }
}

1. while中是<=，而不是<

在上面代码中，right的初始值为nums.length-1，是最后一个元素的索引，而不是nums.length。这两者看似一致，但实际有区别：

right初始化为nums.length-1，相当于查找的区间是闭区间[left, right]。而right初始化为nums.length，查找的区间就变成左闭右开了[left,right)，因为nums.length是越界的。

搜索停止的条件是nums[mid]===target。但如果没找到，就当搜索区间为空时，跳出while循环。