二分查找算法

基本原理

二分查找是一种在有序数组中查找特定元素的高效算法，通过反复将搜索区间对半分割来快速定位目标值。

算法步骤

1. 确定搜索范围 - 设置左右边界
2. 计算中点 - mid = (left + right) / 2
3. 比较判断 - 将中点值与目标值比较
4. 缩小范围 - 根据比较结果调整边界
5. 重复执行 - 直到找到目标或搜索范围为空

基本实现

function binarySearch(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; // 找到目标，返回索引
    } else if (arr[mid] < target) {
      left = mid + 1; // 目标在右半部分
    } else {
      right = mid - 1; // 目标在左半部分
    }
  }

  return -1; // 未找到目标
}

// 使用示例
const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(sortedArray, 7)); // 输出: 3
console.log(binarySearch(sortedArray, 6)); // 输出: -1

递归实现

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;
  } else if (arr[mid] < target) {
    return binarySearchRecursive(arr, target, mid + 1, right);
  } else {
    return binarySearchRecursive(arr, target, left, mid - 1);
  }
}

时间复杂度

• 最佳情况 - O(1)：目标元素恰好在中间
• 平均情况 - O(log n)：每次搜索范围减半
• 最坏情况 - O(log n)：搜索到边界才找到或确认不存在

应用场景

• 有序数组查找 - 最基本的应用
• 寻找边界 - 查找第一个/最后一个满足条件的元素
• 峰值查找 - 寻找局部最大值
• 开方运算 - 计算平方根的近似值

注意事项

• 数组必须是有序的
• 注意整数溢出 - 使用 left + (right - left) / 2
• 边界条件处理要准确