Back

在 JavaScript 中实现二分查找

OpenReplay Team OpenReplay Team

Feb 26, 2026 · 2 min read

在 JavaScript 中实现二分查找

假设你正在一个包含 100,000 个商品价格的已排序数组中进行搜索。JavaScript 内置的 indexOf() 方法会从头开始逐个检查每个元素——这可能需要进行 100,000 次比较。而二分查找最多只需要 17 次。这就是为什么 JavaScript 二分查找算法如此重要,也是为什么值得你自己编写它的原因——因为 JavaScript 并没有提供内置的二分查找方法。

本文将介绍二分查找的工作原理、如何实现迭代和递归两种版本,以及何时应该使用它而不是线性查找。

核心要点

  • 二分查找仅适用于已排序数组,时间复杂度为 O(log n),而线性查找为 O(n)。
  • 迭代方法是大多数使用场景的首选——它可读性强、效率高,且空间复杂度为 O(1)。
  • 递归版本虽然优雅,但会消耗 O(log n) 的栈空间,忘记 return 递归调用是一个常见错误。
  • 在应用二分查找之前,务必使用数值比较器((a, b) => a - b)对数字数组进行排序——JavaScript 默认的 sort() 方法是按字典序排序的。

什么是二分查找?为什么它需要已排序数组?

二分查找是一种分治算法。它通过反复将搜索空间减半,直到找到目标值或穷尽所有可能性。

关键在于:它只适用于已排序数组。该算法假设如果目标值大于中间元素,它必定在右半部分。这个假设在未排序数据上完全不成立——你会得到错误的结果而不会报错。

步骤如下:

  1. 找到当前搜索范围的中间元素
  2. 如果它等于目标值,返回其索引
  3. 如果目标值较小,搜索左半部分
  4. 如果目标值较大,搜索右半部分
  5. 重复以上步骤,直到找到目标或搜索范围为空

在 JavaScript 中实现二分查找:迭代方法

迭代版本使用 while 循环和两个指针。这是大多数情况下的首选方法——可读性强、效率高,且空间复杂度为 O(1)。

function binarySearch(arr, target) {
  let start = 0
  let end = arr.length - 1

  while (start <= end) {
    const mid = Math.floor((start + end) / 2)

    if (arr[mid] === target) {
      return mid // 返回索引
    } else if (arr[mid] < target) {
      start = mid + 1 // 搜索右半部分
    } else {
      end = mid - 1 // 搜索左半部分
    }
  }

  return -1 // 未找到目标
}

const prices = [10, 25, 47, 89, 134, 200]
console.log(binarySearch(prices, 89))  // 3
console.log(binarySearch(prices, 50))  // -1

注意,这个函数返回的是目标值的索引,而不是布尔值。在实际应用中,这几乎总是更有用的。

JavaScript 中的递归二分查找

递归版本在每次调用时传递更新后的边界索引。它虽然优雅,但会使用 O(log n) 的栈空间——每次递归调用都会占用一个栈帧。

function binarySearchRecursive(arr, target, start = 0, end = arr.length - 1) {
  if (start > end) return -1

  const mid = Math.floor((start + end) / 2)

  if (arr[mid] === target) return mid

  return arr[mid] < target
    ? binarySearchRecursive(arr, target, mid + 1, end)
    : binarySearchRecursive(arr, target, start, mid - 1)
}

const scores = [3, 11, 22, 45, 67, 91]
console.log(binarySearchRecursive(scores, 22))  // 2
console.log(binarySearchRecursive(scores, 50))  // -1

一个常见错误:忘记 return 递归调用。如果没有 return,即使元素存在,函数也会返回 undefined。

搜索前先排序

如果你的数组还没有排序,你需要先对它进行排序。JavaScript 默认的 Array.sort() 方法是按字典序排序的,这会破坏数值比较:

[10, 9, 100].sort()                   // [10, 100, 9] — 错误
[10, 9, 100].sort((a, b) => a - b)    // [9, 10, 100] — 正确

在运行二分查找之前,务必对数字数组使用数值比较器。

二分查找 vs 线性查找:何时使用哪种?

线性查找二分查找
数组必须排序否是
时间复杂度O(n)O(log n)
适合小数组✅❌
适合大数组❌✅
多次搜索低效高效

对于一个包含 10,000 个元素的数组,线性查找最多需要 10,000 次比较。二分查找最多只需要 14 次。如果你只需要在一个小型未排序数组中搜索一次,indexOf() 就足够了。如果你需要在大型已排序数据中重复搜索,二分查找才是正确的工具。

总结

一旦理解了已排序数组的要求,在 JavaScript 中实现二分查找就很简单了。默认使用迭代版本——它更简洁,避免了调用栈开销。当你的代码结构从递归中受益时再使用递归版本,但要记得始终 return 递归调用。并且在搜索之前,务必验证你的数组已使用正确的数值比较器进行了排序。

常见问题

是的,只要字符串数组按字母顺序排序,二分查找就适用。JavaScript 中的比较运算符默认按字典序处理字符串比较,因此相同的算法逻辑也适用。只需确保使用默认的 sort 方法对数组进行排序,该方法已经按字典序对字符串进行排序。

JavaScript 数组设计得很灵活,可以容纳混合类型,这使得内置二分查找变得不切实际,因为它需要一个已排序的、类型统一的集合。像 Lodash 这样的库为此提供了 sortedIndexOf 方法,但对于原生 JavaScript,你需要自己编写实现。

标准实现会返回一个匹配元素的索引,但不一定是第一个或最后一个出现的位置。如果你需要重复值的第一个或最后一个索引,必须修改算法,使其在找到匹配项后继续在左半部分或右半部分搜索。

两者的时间复杂度都是 O(log n),因此它们的原始速度几乎相同。但是,迭代版本避免了递归函数调用的开销,并使用恒定的内存,这使得它在实践中稍微更高效。对于非常深的递归,递归版本还可能面临栈溢出的风险。

Complete picture for complete understanding

Capture every clue your frontend is leaving so you can instantly get to the root cause of any issue with OpenReplay — the open-source session replay tool for developers. Self-host it in minutes, and have complete control over your customer data.

Check our GitHub repo and join the thousands of developers in our community.

OpenReplay

More articles from OpenReplay Blog