二分查找（Binary Search）是一种经典的算法，用于在 有序数组 中高效地查找目标元素。它的时间复杂度为 O(log n)，相比于线性查找的 O(n)，在处理大量数据时具有显著的优势。本文将详细介绍二分查找的实现原理、应用场景，并讨论一些优化技巧，帮助你更好地理解与应用这一高效搜索算法。

什么是二分查找？

二分查找是一种分治法的典型应用。其核心思想是：在每次查找时，将搜索空间一分为二，利用数组的有序性，通过比较中间元素与目标值的大小来缩小查找范围，从而有效地减少每次查找的元素数。

二分查找的基本实现

以下是二分查找的基本实现代码：

function binarySearch(arr: number[], target: number): number {
  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; // 未找到目标值
}

解释：

• left 和 right 分别指向数组的起始和结束位置。
• mid 是每次查找的中间索引。通过 Math.floor((left + right) / 2) 计算中间元素。
• 比较 arr[mid] 和目标值 target，决定接下来要查找左半部分还是右半部分。
• 当 left > right 时，意味着整个数组已经查找完毕而没有找到目标值。

二分查找的递归实现

除了迭代方式，还可以通过递归来实现二分查找：

function binarySearchRecursive(arr: number[], target: number, left: number, right: number): number {
  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); // 查找左半部分
  }
}

递归 vs. 迭代：

• 递归实现 代码更加简洁，但递归深度受限于栈空间。
• 迭代实现 更常见，在空间复杂度上表现更优，因为它避免了递归调用的额外开销。

二分查找的应用场景

二分查找广泛应用于需要在有序结构中进行高效查找的场景。常见应用包括：

1. 查找有序数组中的元素：如经典的查找问题，在有序数组中快速找到目标元素的位置。
2. 搜索插入位置：在某些情况下，需要找到一个元素的插入位置以保持数组有序，这也可以通过二分查找来实现。
3. 求解区间问题：如求解满足某一条件的最大或最小值，也可以通过二分查找快速逼近目标。

二分查找的优化与变种

1. 防止溢出

在处理非常大的数组时，直接计算 mid 可能会导致整数溢出。可以通过以下方式避免：

const mid = left + Math.floor((right - left) / 2);

这种写法避免了 left + right 的直接相加，减少了溢出风险。

2. 查找第一个或最后一个匹配的元素

如果数组中有重复元素，二分查找的基本实现只能找到其中任意一个匹配项。如果我们需要查找第一个或最后一个匹配的元素，可以做如下修改：

查找第一个匹配的元素：

function findFirst(arr: number[], target: number): number {
  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) {
      result = mid; // 找到元素，继续向左侧查找
      right = mid - 1;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
}

查找最后一个匹配的元素：

function findLast(arr: number[], target: number): number {
  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) {
      result = mid; // 找到元素，继续向右侧查找
      left = mid + 1;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
}

3. 寻找有序旋转数组中的最小值

如果给定的数组是一个有序旋转数组，即在某个点进行旋转后形成的数组，二分查找同样可以应用来找到最小值：

function findMinInRotatedArray(arr: number[]): number {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] > arr[right]) {
      left = mid + 1; // 最小值在右侧
    } else {
      right = mid; // 最小值在左侧
    }
  }

  return arr[left]; // 返回最小值
}

二分查找的局限性

虽然二分查找高效，但它并非适用所有场景：

• 数组必须有序：这是二分查找的前提条件，未排序的数组需要先排序，可能增加额外的 O(n log n) 开销。
• 动态数据集：如果数据集频繁更新（如插入、删除操作），维护有序性会比较麻烦。
• 离散数据结构：二分查找通常用于连续存储的数组，链表等非连续数据结构不适用。