js实现二分查找

二分查找的原理

二分查找是一种在有序数组中查找特定元素的算法。通过每次将搜索区间减半，快速定位目标值的位置。时间复杂度为O(log n)，远优于线性搜索的O(n)。

递归实现

递归方式通过不断缩小搜索范围实现二分查找。需要定义左右边界作为参数，基准条件为左边界超过右边界。

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) return -1;

  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid;

  return arr[mid] > target 
    ? binarySearchRecursive(arr, target, left, mid - 1)
    : binarySearchRecursive(arr, target, mid + 1, right);
}

迭代实现

迭代版本通过while循环调整左右指针位置，避免递归调用带来的栈开销。更适用于大规模数据。

function binarySearchIterative(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;

    arr[mid] > target 
      ? right = mid - 1
      : left = mid + 1;
  }
  return -1;
}

边界条件处理

需特别注意数组为空、目标值超出范围等情况。以下代码添加了前置校验：

function binarySearchWithCheck(arr, target) {
  if (!arr.length || target < arr[0] || target > arr[arr.length - 1]) {
    return -1;
  }
  // 后续使用迭代或递归实现
}

变体应用

查找第一个匹配项时，需要在找到目标值后继续向左搜索：

function findFirstOccurrence(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = -1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] >= target) {
      if (arr[mid] === target) result = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return result;
}

性能注意事项

使用位运算计算中点可提升性能： const mid = (left + right) >>> 1 等效于 Math.floor((left + right) / 2)，但避免浮点数转换。