二分查找：原理、实现、应用与注意事项

二分查找（Binary Search）是一种高效的查找算法，适用于在有序数组中查找特定元素。它的时间复杂度为 O(log n)，相比线性查找的 O(n)，在处理大规模数据时性能优势明显。

1. 理解二分查找

二分查找的核心思想是分治：通过不断将查找范围缩小一半，快速定位目标元素。具体步骤如下：

1. 初始化：定义左右边界 left 和 right，分别指向数组的起始和末尾。
2. 计算中间位置：取中间索引 mid = Math.floor((left + right) / 2)。
3. 比较中间元素：
   • 如果中间元素等于目标值，返回索引。
   • 如果中间元素小于目标值，说明目标值在右半部分，更新 left = mid + 1。
   • 如果中间元素大于目标值，说明目标值在左半部分，更新 right = mid - 1。
4. 重复步骤 2-3，直到找到目标值或 left > right（未找到）。

2. 实现二分查找

以下是 JavaScript 实现：

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 arr = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(arr, 7)); // 输出: 3
console.log(binarySearch(arr, 10)); // 输出: -1

3. 应用场景

二分查找适用于以下场景：

1. 有序数组查找：如查找某个数是否在排序后的数组中。
2. 边界查找：如查找第一个大于等于目标值的元素（变种问题）。
3. 数值计算：如求解平方根、指数等数学问题。
4. 数据库索引：数据库的 B+ 树索引利用了二分查找的思想。
5. 算法优化：在分治算法（如归并排序、快速排序）中，二分查找常用于优化子问题的处理。

4. 变种问题

二分查找的变种问题在实际开发中也很常见：

• 查找第一个等于目标值的元素：

  function findFirst(arr, target) {
      let left = 0;
      let right = arr.length - 1;
  
      while (left <= right) {
          const mid = Math.floor((left + right) / 2);
          if (arr[mid] >= target) {
              right = mid - 1;
          } else {
              left = mid + 1;
          }
      }
  
      return arr[left] === target ? left : -1;
  }
  

• 查找最后一个等于目标值的元素：

  function findLast(arr, target) {
      let left = 0;
      let right = arr.length - 1;
  
      while (left <= right) {
          const mid = Math.floor((left + right) / 2);
          if (arr[mid] <= target) {
              left = mid + 1;
          } else {
              right = mid - 1;
          }
      }
  
      return arr[right] === target ? right : -1;
  }
  

5. 注意事项

• 数组必须有序：二分查找的前提是数组有序，否则无法保证正确性。
• 边界条件：注意处理 left 和 right 的更新，避免死循环或越界。
• 整数溢出：在计算 mid 时，left + right 可能导致整数溢出，建议使用 left + Math.floor((right - left) / 2)。

总结

二分查找是一种高效的查找算法，适用于有序数组。掌握其核心思想和实现方法，能够帮助你在实际开发中快速解决查找问题，并优化算法性能。