二分查找

二分查找（Binary Search）是一种高效的查找算法，它利用了已排序数组的特性，通过每次将查找范围缩小一半的方式，快速定位目标元素。二分查找的时间复杂度为 O(log n)，相比于线性查找的 O(n)，在大规模数据集上具有显著优势。

基本原理

二分查找的核心思想是：

1. 在已排序的数组中，取中间位置的元素进行比较
2. 如果目标值等于中间元素，则查找成功
3. 如果目标值小于中间元素，则在左半部分继续查找
4. 如果目标值大于中间元素，则在右半部分继续查找
5. 重复上述步骤，直到找到目标值或确定目标值不存在

JavaScript 实现

迭代实现

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    // 计算中间索引（避免整数溢出的写法）
    const mid = left + Math.floor((right - left) / 2);
    
    // 找到目标值
    if (arr[mid] === target) {
      return mid;
    }
    
    // 在左半部分查找
    if (arr[mid] > target) {
      right = mid - 1;
    } 
    // 在右半部分查找
    else {
      left = mid + 1;
    }
  }
  
  // 目标值不存在
  return -1;
}

递归实现

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  // 递归终止条件
  if (left > right) {
    return -1;
  }

  // 计算中间索引（避免整数溢出的写法）
  const mid = left + Math.floor((right - left) / 2);

  // 找到目标值
  if (arr[mid] === target) {
    return mid;
  }

  // 在左半部分查找 
  if (arr[mid] > target) {
    return binarySearchRecursive(arr, target, left, mid - 1); 
  } else {
    // 在右半部分查找
    return binarySearchRecursive(arr, target, mid + 1, right);
  }
}

二分查找的应用场景

1. 数据库索引 : 数据库中的B树和B+树索引结构使用了二分查找的思想
2. 字典查找 : 在有序词典中快速定位单词
3. IP路由表查找 : 在网络路由中查找最匹配的路由条目
4. 机器学习 : 在决策树等算法中用于快速定位分割点
5. 图像处理 : 在某些图像处理算法中用于快速定位特定像素值

二分查找的局限性

1. 要求有序数据 : 二分查找只适用于已排序的数据集
2. 不适合插入和删除频繁的场景 : 维护有序性会带来额外开销
3. 不适合链表等非随机访问的数据结构 : 二分查找需要O(1)时间的随机访问能力
4. 对于小规模数据集优势不明显 : 在小数据集上，线性查找可能更快

时间复杂度分析

• 最坏情况 : O(log n) - 目标值在最后一次比较时找到或不存在
• 平均情况 : O(log n)
• 最好情况 : O(1) - 目标值恰好是中间元素

空间复杂度分析

• 迭代实现 : O(1) - 只需要常数级别的额外空间
• 递归实现 : O(log n) - 递归调用栈的深度

总结

二分查找是一种高效的查找算法，特别适合在大型有序数据集上进行查找操作。它的对数级时间复杂度使其在处理大规模数据时具有显著优势。虽然二分查找有一些局限性，但在适合的场景下，它仍然是最优选择之一。掌握二分查找及其变种，对于解决实际问题和算法面试都非常有帮助。