二分查找算法详解

什么是二分查找

二分查找（Binary Search）是在有序数组里查找目标值的算法。它每次取当前查找区间的中间元素与目标比较，根据大小关系把查找区间砍掉一半，重复这个过程直到找到目标或者区间为空。

前提条件只有一个但很关键：数组必须有序。如果数组无序，二分查找的结果是错的，而且它不会报错，只会安静地返回 -1，这是实际使用中最容易踩的坑。

为什么需要它

在一个长度为 n 的数组里顺序查找，最坏情况要比较 n 次，时间复杂度 O(n)。二分查找每次把区间减半，最多比较 log₂n 次，时间复杂度 O(logN)，空间复杂度 O(1)（迭代写法）。

这个差距在数据量大的时候非常明显：100 万个元素，顺序查找最坏 100 万次比较，二分查找只需要约 20 次。

迭代实现

我们用两个指针 low 和 high 维护当前的查找区间 [low, high]，每轮算出中点 mid 与目标比较：

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const cur = arr[mid];
    if (cur === target) {
      return mid;
    }
    if (cur < target) {
      // 目标在右半区，抛弃左半区（含 mid）
      low = mid + 1;
    } else {
      // 目标在左半区，抛弃右半区（含 mid）
      high = mid - 1;
    }
  }
  return -1;
}

const arr = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(arr, 9)); // 4
console.log(binarySearch(arr, 8)); // -1

这里有三个细节值得单独说：

循环条件是 low <= high 而不是 low < high。当区间收缩到只剩一个元素时 low === high，这个元素也必须被检查到，用 < 会漏掉它。

更新指针时必须写 mid + 1 和 mid - 1，不能写 low = mid。因为 mid 这个位置已经比较过并且确定不是目标，如果不排除它，当区间只剩两个元素时 mid 会一直等于 low，low 不再变化，程序进入死循环。

Math.floor 不能省。JS 里 / 是浮点除法，(0 + 3) / 2 得到 1.5，用它当下标取到的是 undefined。也可以用位运算 (low + high) >> 1 代替，效果相同且更快，但要注意 >> 会把操作数转成 32 位有符号整数。

递归实现

递归写法逻辑更直白，但每层调用都占一个栈帧，空间复杂度变成 O(logN)：

function binarySearchRecursive(arr, target, low = 0, high = arr.length - 1) {
  if (low > high) return -1;
  const mid = (low + high) >> 1;
  if (arr[mid] === target) return mid;
  return arr[mid] < target
    ? binarySearchRecursive(arr, target, mid + 1, high)
    : binarySearchRecursive(arr, target, low, mid - 1);
}

查找插入位置（左边界）

实际业务里更常用的不是「找到没有」，而是「如果要插入，该插在哪」，或者「找第一个大于等于 target 的位置」。这类问题用左闭右开区间写更顺：

// 返回第一个 >= target 的下标，若都小于 target 则返回 arr.length
function lowerBound(arr, target) {
  let low = 0;
  let high = arr.length; // 注意是 length，不是 length - 1
  while (low < high) {
    const mid = (low + high) >> 1;
    if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid; // 注意不是 mid - 1
    }
  }
  return low;
}

console.log(lowerBound([1, 3, 3, 3, 5], 3)); // 1
console.log(lowerBound([1, 3, 3, 3, 5], 4)); // 4

这个版本的区间是 [low, high)，右端是开的，所以循环条件是 low < high，high 的更新是 mid 而不是 mid - 1。两套写法混着用是二分查找出 bug 的头号原因，选一套坚持用，不要在同一个函数里两种区间约定混搭。

数组中的 indexOf 对比

Array.prototype.indexOf 是顺序扫描，O(n)，对无序数组也能用。二分查找要求有序，换来 O(logN)。所以判断该用哪个的标准很简单：数据本来就有序（或者查询次数远大于插入次数，值得先排一次序）就用二分，否则用 indexOf。

单次查找不要为了用二分而先排序，排序本身是 O(nlogn)，比直接顺序扫一遍还慢。