二分搜索框架

框架

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

计算中间mid 使用(left + right) / 2的结果和left + (right -left) / 2的结果相同，但是如果left和right太大，直接相加会导致整型溢出。写成left + (right -left) / 2则不会溢出

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

搜索一个数，如果存在则返回它的索引，否则返回-1

const binarySearch = (nums, target) => {
  let left = 0;
  let right = nums.length - 1
  while (left <= right) {
    const 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
    }
  }
  return -1
}