二分查找算法

二分查找是一种在有序数组中查找特定元素的高效算法。它的核心思想是通过不断将搜索区间减半来快速定位目标值。下面我将详细讲解二分查找的原理、步骤、边界处理以及代码实现。

1. 基本思想与适用条件

• 核心思想：利用数组的有序性，每次比较目标值与区间中间元素的大小，从而将搜索范围缩小一半。
• 前提条件：
  1. 数组必须是有序的（升序或降序）。
  2. 数组支持随机访问（即通过下标直接访问元素）。
• 时间复杂度：O(log n)，远优于线性查找的 O(n)。

2. 算法步骤详解（以升序数组为例）

假设在有序数组 arr 中查找目标值 target，初始化搜索区间为整个数组：

1. 初始化指针：

   • 左边界 left = 0（指向第一个元素）
   • 右边界 right = n-1（指向最后一个元素，n 为数组长度）

2. 循环条件：

   • 当 left <= right 时，说明区间有效，继续搜索。若 left > right，则说明目标不存在。

3. 计算中间位置：

   • 取中间下标 mid = left + (right - left) // 2。
     （使用此公式而非 (left + right) // 2 可防止整数溢出）

4. 比较与调整边界：

   • 若 arr[mid] == target：找到目标，返回 mid。
   • 若 arr[mid] < target：说明目标在右侧，调整左边界 left = mid + 1。
   • 若 arr[mid] > target：说明目标在左侧，调整右边界 right = mid - 1。

5. 终止条件：

   • 找到目标时直接返回下标。
   • 若循环结束仍未找到，返回 -1 表示目标不存在。

3. 关键细节与边界处理

• 为什么是 left <= right？
  如果区间为 [left, right]（闭区间），则 left == right 时区间仍包含一个元素，需继续判断。若改为 left < right，会漏查单个元素的情况。

• 为什么调整边界时是 mid ± 1？
  因为 arr[mid] 已经确定不是目标，下一步应直接排除 mid 位置，搜索其左侧或右侧区间，避免重复判断。

• 防止整数溢出：
  计算 mid 时使用 left + (right - left) // 2 而非 (left + right) // 2，可确保在 left 和 right 很大时不会溢出。

4. 代码实现（Python示例）

def binary_search(arr, target):
    left, right = 0, len(arr) - 1  # 初始化闭区间 [left, right]
    
    while left <= right:
        mid = left + (right - left) // 2  # 防溢出
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1  # 目标在右侧，缩小至 [mid+1, right]
        else:
            right = mid - 1  # 目标在左侧，缩小至 [left, mid-1]
    
    return -1  # 未找到

5. 变体问题举例

二分查找有多种变体，例如：

• 查找第一个等于目标的值：当 arr[mid] == target 时，不直接返回，而是继续向左边界收缩（right = mid - 1）。
• 查找最后一个等于目标的值：类似地，向右边界收缩（left = mid + 1）。
• 查找第一个大于等于目标的值：结合比较条件调整边界。

这些变体需根据具体问题微调循环条件和边界操作，但核心思想仍是“逐步减半”。