JavaScript中实现二分查找的方法详解

二分查找是一种高效的查找算法，适用于已经排好序的数组。它的核心逻辑是每次将查找区间缩小一半，从而快速定位目标值的位置，时间复杂度为O(log n)，远低于线性查找的O(n)。下面我们就来看看如何在JavaScript中实现二分查找。

二分查找的基本原理

二分查找的执行流程可以总结为以下几步：

• 设定查找区间的左右边界，初始时左边界为数组第一个元素的索引，右边界为数组最后一个元素的索引
• 计算中间位置的索引，取出中间元素的值
• 如果中间元素等于目标值，直接返回中间位置索引
• 如果中间元素小于目标值，说明目标值只可能在右半区间，将左边界更新为中间位置加1
• 如果中间元素大于目标值，说明目标值只可能在左半区间，将右边界更新为中间位置减1
• 重复上述过程，直到左边界大于右边界，说明数组中不存在目标值，返回-1

迭代方式实现二分查找

迭代方式是二分查找最常见的实现形式，通过循环不断缩小查找范围，直到找到目标值或者确定不存在目标值。下面是完整的代码示例：

/**
 * 迭代方式实现二分查找
 * @param {Array} arr 已排序的数组，升序排列
 * @param {number} target 要查找的目标值
 * @returns {number} 目标值在数组中的索引，不存在则返回-1
 */
function binarySearchIterative(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    // 计算中间位置，使用位运算避免(left + right)可能溢出的问题
    const mid = left + Math.floor((right - left) / 2);
    const midVal = arr[mid];

    if (midVal === target) {
      // 找到目标值，返回索引
      return mid;
    } else if (midVal < target) {
      // 目标值在右半区间，更新左边界
      left = mid + 1;
    } else {
      // 目标值在左半区间，更新右边界
      right = mid - 1;
    }
  }

  // 循环结束仍未找到，返回-1
  return -1;
}

// 测试用例
const sortedArr = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearchIterative(sortedArr, 7)); // 输出：3
console.log(binarySearchIterative(sortedArr, 4)); // 输出：-1

上面的代码中，我们通过while循环不断调整左右边界，每次循环都将查找范围缩小一半。这里计算中间位置时没有直接使用(left + right) / 2，而是采用left + Math.floor((right - left) / 2)的方式，避免了当left和right都很大时可能产生的数值溢出问题，在实际开发中更推荐这种写法。

递归方式实现二分查找

除了迭代方式，我们也可以使用递归来实现二分查找，递归的思路是将每次的查找区间作为参数传递给下一次递归调用，直到找到目标值或者区间为空。代码如下：

/**
 * 递归方式实现二分查找
 * @param {Array} arr 已排序的数组，升序排列
 * @param {number} target 要查找的目标值
 * @param {number} left 当前查找区间的左边界
 * @param {number} right 当前查找区间的右边界
 * @returns {number} 目标值在数组中的索引，不存在则返回-1
 */
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  // 递归终止条件：区间为空，说明不存在目标值
  if (left > right) {
    return -1;
  }

  // 计算中间位置
  const mid = left + Math.floor((right - left) / 2);
  const midVal = arr[mid];

  if (midVal === target) {
    // 找到目标值，返回索引
    return mid;
  } else if (midVal < target) {
    // 目标值在右半区间，递归查找右半部分
    return binarySearchRecursive(arr, target, mid + 1, right);
  } else {
    // 目标值在左半区间，递归查找左半部分
    return binarySearchRecursive(arr, target, left, mid - 1);
  }
}

// 测试用例
const testArr = [2, 4, 6, 8, 10, 12, 14];
console.log(binarySearchRecursive(testArr, 10)); // 输出：4
console.log(binarySearchRecursive(testArr, 5)); // 输出：-1

递归实现的代码逻辑和迭代方式一致，只是把循环改成了递归调用。递归方式写起来更简洁，但是需要注意递归深度的问题，如果数组长度非常大，可能会导致栈溢出，这种情况下更推荐使用迭代方式。

两种实现方式的对比

注意事项

使用二分查找时需要注意两个核心前提：第一，数组必须是已经排好序的，通常是升序排列，如果是降序数组，需要调整比较逻辑；第二，数组中的元素应该是可比较的，对于复杂类型的数组，需要自定义比较规则。如果数组未排序，需要先进行排序再使用二分查找，否则无法得到正确结果。

JavaScript二分查找迭代实现递归实现算法复杂度O_log_n 本作品最后修改时间：2026-05-23 23:01:55