详解二分查找

前言

1. 二分查找是一种高效的查找算法，适用于在有序数组中查找特定元素。它通过将搜索范围逐步缩小一半来实现快速查找,二分查找的时间复杂度为 O(log n)，相比于线性查找的 O(n) 具有显著的性能优势。

二分查找的细节处理

虽然二分查找的基本思想简单，但在实际编写中不免存在一些细节边界问题。这里总结了 4 个细节：

1. 目标值的区间定义（一般分为左闭右开和左闭右闭，这会影响后续三个细节以及最终代码实现）
2. 循环的终止条件（left <= right 和 left < right）
3. 中间值的计算方式（使用 mid = left + ((right - left) >> 1) 防止溢出）
4. 左右边界的更新方式（在 nums[mid] 大于或小于 target 时，left 和 right 如何更新）

目标值的区间定义

区间的定义这就决定了二分法的代码应该如何写

1. 左闭右开：[left, right)：定义 target 在 [left, right) 区间，也就是left == right无意义。此时有以下两点：

   • while (left < right) 要使用 <。因为左闭右开，右边界不可达，left == right无意义，所以使用 <
   • if (nums[mid] > target)时 right 要赋值为 mid。当前 nums[mid] 已经比较过且不等于 target，要去左区间继续寻找，同时寻找区间是左闭右开区间，所以 right 更新为 mid（右边界不可达，此时下一个查询区间不会去重复比较 nums[mid]）

2. 左闭右闭：[left, right]：定义 target 在[left, right]区间，也就是可能存在 left == right的情况。此时有以下两点：

   • while (left <= right) 要使用 <=。因为left == right是有意义的，当 left == right 时可能刚好也等于 target，要继续查找，所以使用 <=
   • if (nums[mid] > target) 时 right 要赋值为 mid - 1。因为左闭右闭区间右边界可达，当前这个 nums[mid] 一定不是（大于） target，为避免重复比较 nums[mid]，那么接下来要查找的左区间结束下标位置（右边界）需要更新为 mid - 1，

左闭右开的二分查找代码实现

// 左闭右开二分查找
const binarySearch = (nums, target) => {
  let left = 0
  // 定义target在左闭右开的区间里，即：[left, right)
  // 右边不可达，所以这里是 nums.length而不是 nums.length - 1
  let right = nums.length

  // 因为左闭右开不可能存在 left == right，所以循环终止条件是 left < right
  while (left < right) {
    const mid = (left + (right - left) / 2) | 0 // 防止溢出
    if (nums[mid] === target) return mid // 找到目标值，直接返回下标

    if (nums[mid] < target) {
      // 不管左闭右开还是左闭右闭，左边都是可达的，所以更新左边界为 mid + 1，防止重复比较 mid
      left = mid + 1
    } else {
      right = mid // 左闭右开，同理更新右边界为 mid
    }
  }

  return nums[left] === target ? left : -1
}