二分查找（Binary Search）一种高效地查找算法

2026-09-12 · 算法 · 阅读 2 · 访客 1

二分查找（Binary Search）是一种高效的查找算法，适用于在有序数组中查找特定元素。它的核心思想是通过不断将搜索范围缩小一半来快速定位目标元素。以下是二分查找的详细讲解：

1. 基本思想

二分查找的前提是数组必须是有序的（升序或降序）。算法通过以下步骤实现：

  1. 确定搜索范围：初始时，搜索范围是整个数组。
  2. 计算中间位置：找到搜索范围的中间元素。
  3. 比较中间元素：
    • 如果中间元素等于目标值，查找成功。
    • 如果中间元素大于目标值，缩小搜索范围到左半部分。
    • 如果中间元素小于目标值，缩小搜索范围到右半部分。
  4. 重复步骤 2-3：直到找到目标值或搜索范围为空。

2. 算法步骤

以下是二分查找的具体步骤：

  1. 初始化两个指针：left 指向数组起始位置，right 指向数组末尾位置。
  2. 计算中间位置：mid = left + (right - left) // 2。
  3. 比较中间元素 arr[mid] 与目标值 target：
    • 如果 arr[mid] == target，返回 mid。
    • 如果 arr[mid] < target，更新 left = mid + 1。
    • 如果 arr[mid] > target，更新 right = mid - 1。
  4. 重复步骤 2-3，直到 left > right，此时查找失败，返回 -1。

3. 代码实现

以下是二分查找的 Python 实现：

def binary_search(arr, target):
    left, right = 0, len(arr) - 1  # 初始化搜索范围
    while left <= right:
        mid = left + (right - left) // 2  # 计算中间位置
        if arr[mid] == target:  # 找到目标值
            return mid
        elif arr[mid] < target:  # 目标值在右半部分
            left = mid + 1
        else:  # 目标值在左半部分
            right = mid - 1
    return -1  # 未找到目标值

# 示例
arr = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(arr, target)
print(f"目标值 {target} 的索引是: {result}")

4. 时间复杂度

二分查找的时间复杂度是 O(log n)，其中 n 是数组的长度。这是因为每次查找都将搜索范围缩小一半，最多需要 log₂n 次比较。

5. 空间复杂度

二分查找的空间复杂度是 O(1)，因为它只使用了常数级别的额外空间（如指针变量）。

6. 优缺点

优点

  • 高效：时间复杂度为 O(log n)，远优于线性查找的 O(n)。
  • 简单：实现逻辑清晰，代码简洁。

缺点

  • 要求有序数组：必须对数组进行排序，排序的时间复杂度通常为 O(n log n)。
  • 不适合动态数据：如果数据频繁插入或删除，维护有序数组的成本较高。

7. 变种与应用

二分查找有多种变种，适用于不同的场景：

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

  • 在找到目标值后，继续向左搜索。
def binary_search_first(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] >= target:
            right = mid - 1
        else:
            left = mid + 1
    if left < len(arr) and arr[left] == target:
        return left
    return -1

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

  • 在找到目标值后，继续向右搜索。
def binary_search_last(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid - 1
    if right >= 0 and arr[right] == target:
        return right
    return -1

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

  • 适用于查找插入位置。
def binary_search_insert(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] >= target:
            right = mid - 1
        else:
            left = mid + 1
    return left

8. 应用场景

  • 查找有序数组中的元素：如查找字典中的单词、电话号码等。
  • 查找边界值：如查找第一个或最后一个等于目标值的元素。
  • 数值计算：如在单调函数中查找满足条件的值。

9. 总结

二分查找是一种高效的查找算法，适用于有序数组。它的核心思想是通过不断缩小搜索范围来快速定位目标值，时间复杂度为 O(log n)，空间复杂度为 O(1)。在实际应用中，二分查找的变种可以解决多种查找问题，是算法设计和优化中的重要工具。

目录