JavaScript 实现二分查找算法详解

近期在面试过程中，常被要求手写实现二分查找算法。尽管对二分查找的概念和原理并不陌生，但在实际编码时仍容易出错。借此机会重新梳理并复习这一基础算法。对于前端开发者而言，虽然大多数公司不要求掌握极其复杂的算法，但掌握基本的数据结构和常见算法的手写实现仍是必备技能。

二分查找的定义

二分查找是一种针对有序数组设计的目标元素查找算法。其核心逻辑是：每次取数组中间元素与目标值进行比较。若两者相等，则返回该中间元素的索引；若不相等，则根据比较结果确定目标元素位于左半部分还是右半部分，从而缩小查找范围。该过程重复进行，直至找到目标元素或查找区间为空。二分查找的时间复杂度为 O(log n)，其中 n 为数组长度，其效率显著高于顺序查找的 O(n)。

二分查找的代码实现

以下展示使用 JavaScript 编写的二分查找代码。函数接收两个参数：arr 代表已排序的数组，target 代表需要查找的目标值。函数执行后返回 target 在 arr 中的索引位置；若数组中不存在该目标值，则返回 -1。

// 定义二分查找函数
function binarySearch(arr, target) {
  // 定义查找范围的左右边界
  let left = 0;
  let right = arr.length - 1;
  // 当左边界小于等于右边界时，继续查找
  while (left <= right) {
    // 计算中间元素的索引
    let mid = Math.floor((left + right) / 2);
    // 如果中间元素等于目标元素，返回索引
    if (arr[mid] === target) {
      return mid;
    }
    // 如果中间元素小于目标元素，说明目标元素在右半部分，将左边界移动到中间元素的右边
    else if (arr[mid] < target) {
      left = mid + 1;
    }
    // 如果中间元素大于目标元素，说明目标元素在左半部分，将右边界移动到中间元素的左边
    else {
      right = mid - 1;
    }
  }
  // 如果查找范围为空，说明目标元素不存在，返回-1
  return -1;
}

// 测试代码
let arr = [1, 3, 5, 7, 9, 11, 13, 15]; // 定义一个有序数组
let target = 9; // 定义要查找的元素
let index = binarySearch(arr, target); // 调用二分查找函数
console.log(index); // 输出结果，应该是4

二分查找的实现逻辑解析

• 第一步，初始化查找范围的边界。左边界 left 初始化为 0，右边界 right 初始化为数组长度减 1（即 arr.length - 1），覆盖整个数组区间。
• 第二步，计算当前查找范围中间元素的索引。通过公式 Math.floor((left + right) / 2) 计算得出，即左边界与右边界之和除以 2 后向下取整。例如，当 left 为 0，right 为 7 时，中间索引为 (0 + 7) / 2 = 3.5，向下取整后为 3。
• 第三步，将中间元素 arr[mid] 与目标值 target 进行比较。如果两者相等，说明已找到目标元素，直接返回中间索引 mid；如果不相等，则需根据大小关系调整查找范围。
• 第四步，根据比较结果更新边界以缩小范围。若中间元素小于目标值（arr[mid] < target），说明目标值位于中间元素的右侧，此时将左边界 left 更新为 mid + 1，右边界 right 保持不变；若中间元素大于目标值（arr[mid] > target），说明目标值位于中间元素的左侧，此时将右边界 right 更新为 mid - 1，左边界 left 保持不变。无论哪种情况，查找范围均缩小约一半。
• 重复第2步到第4步，直到找到目标元素或者查找范围为空，如果查找范围为空，说明目标元素不存在，返回-1。

总结

本文阐述了二分查找的基本定义、时间复杂度特性、具体实现步骤以及 JavaScript 代码示例。

二分查找适用于有序数组的目标元素查找，其时间复杂度为 O(log n)，相比顺序查找的 O(n) 具有更高的效率。

其核心实现原理在于通过不断比较中间元素与目标值，根据比较结果动态调整左右边界，从而逐步缩小查找区间，直至定位目标或确认不存在。

以上就是关于使用 JavaScript 实现二分查找算法的详细介绍。如需了解更多 JS 二分查找相关内容，建议查阅本站历史文章或继续浏览后续系列教程。感谢大家的支持！