手写二分查找算法

问题

二分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法。给定一个升序排列的数组和一个目标值，需要找到目标值在数组中的索引位置，如果不存在则返回 -1。

二分查找的思想是：每次将查找区间缩小一半，通过比较中间元素与目标值的大小关系，决定在左半部分还是右半部分继续查找。

解答

/**
 * 二分查找 - 迭代实现
 * @param {number[]} arr - 有序数组（升序）
 * @param {number} target - 目标值
 * @return {number} 目标值的索引，不存在返回 -1
 */
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    // 计算中间位置，使用 Math.floor 向下取整
    // 使用 left + (right - left) / 2 可以避免大数溢出
    const mid = Math.floor(left + (right - left) / 2);
    
    if (arr[mid] === target) {
      // 找到目标值，返回索引
      return mid;
    } else if (arr[mid] < target) {
      // 目标值在右半部分，移动左指针
      left = mid + 1;
    } else {
      // 目标值在左半部分，移动右指针
      right = mid - 1;
    }
  }
  
  // 未找到目标值
  return -1;
}

/**
 * 二分查找 - 递归实现
 * @param {number[]} arr - 有序数组（升序）
 * @param {number} target - 目标值
 * @param {number} left - 左边界
 * @param {number} right - 右边界
 * @return {number} 目标值的索引，不存在返回 -1
 */
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  // 递归终止条件
  if (left > right) {
    return -1;
  }
  
  const mid = Math.floor(left + (right - left) / 2);
  
  if (arr[mid] === target) {
    return mid;
  } else if (arr[mid] < target) {
    // 在右半部分继续查找
    return binarySearchRecursive(arr, target, mid + 1, right);
  } else {
    // 在左半部分继续查找
    return binarySearchRecursive(arr, target, left, mid - 1);
  }
}

/**
 * 二分查找变体 - 查找第一个等于目标值的位置
 * @param {number[]} arr - 有序数组（可能有重复元素）
 * @param {number} target - 目标值
 * @return {number} 第一个等于目标值的索引
 */
function binarySearchFirst(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = -1;
  
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    
    if (arr[mid] === target) {
      result = mid;
      // 继续在左半部分查找，寻找第一个位置
      right = mid - 1;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return result;
}

/**
 * 二分查找变体 - 查找最后一个等于目标值的位置
 * @param {number[]} arr - 有序数组（可能有重复元素）
 * @param {number} target - 目标值
 * @return {number} 最后一个等于目标值的索引
 */
function binarySearchLast(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = -1;
  
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    
    if (arr[mid] === target) {
      result = mid;
      // 继续在右半部分查找，寻找最后一个位置
      left = mid + 1;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return result;
}

使用示例

// 示例1：基本二分查找
const arr1 = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(arr1, 7));  // 输出: 3
console.log(binarySearch(arr1, 10)); // 输出: -1

// 示例2：递归实现
console.log(binarySearchRecursive(arr1, 13)); // 输出: 6
console.log(binarySearchRecursive(arr1, 2));  // 输出: -1

// 示例3：查找第一个和最后一个位置（有重复元素）
const arr2 = [1, 2, 3, 3, 3, 3, 4, 5];
console.log(binarySearchFirst(arr2, 3)); // 输出: 2（第一个3的位置）
console.log(binarySearchLast(arr2, 3));  // 输出: 5（最后一个3的位置）

// 示例4：边界情况
console.log(binarySearch([], 5));        // 输出: -1（空数组）
console.log(binarySearch([5], 5));       // 输出: 0（单元素数组）
console.log(binarySearch([1, 2], 1));    // 输出: 0（查找第一个元素）
console.log(binarySearch([1, 2], 2));    // 输出: 1（查找最后一个元素）

关键点

• 前提条件：二分查找要求数组必须是有序的（升序或降序），这是算法能够工作的基础

• 指针移动：使用 left 和 right 两个指针标记查找区间，每次根据中间值与目标值的比较结果移动指针

• 中间位置计算：使用 Math.floor(left + (right - left) / 2) 而不是 (left + right) / 2，可以避免大数相加时的溢出问题

• 循环条件：while (left <= right) 中的等号很重要，确保当区间只剩一个元素时仍能正确判断

• 时间复杂度：O(log n)，每次查找都将问题规模减半，远优于线性查找的 O(n)

• 空间复杂度：迭代实现为 O(1)，递归实现为 O(log n)（递归调用栈）

• 变体应用：可以扩展为查找第一个/最后一个等于目标值的位置、查找第一个大于等于目标值的位置等

• 适用场景：适合静态有序数据的查找，如果数据频繁变动需要频繁排序，可能不是最优选择