跳到主要内容

二分搜索

二分搜索（Binary Search）是一种高效的搜索算法，适用于在有序数组中查找特定元素。它的核心思想是通过不断缩小搜索范围，将时间复杂度降低到 O(log n)，远优于线性搜索的 O(n)。

什么是二分搜索？​

二分搜索是一种分治算法，它通过将搜索范围一分为二来快速定位目标值。假设我们有一个有序数组 arr，我们需要查找目标值 target。二分搜索的步骤如下：

  1. 找到数组的中间元素 mid。
  2. 如果 mid 等于 target，则返回 mid 的索引。
  3. 如果 mid 大于 target，则在左半部分继续搜索。
  4. 如果 mid 小于 target，则在右半部分继续搜索。
  5. 重复上述过程，直到找到目标值或搜索范围为空。
备注

二分搜索的前提是数组必须是有序的。如果数组无序，需要先进行排序。

二分搜索的实现​

以下是一个用 Python 实现的二分搜索示例：

python
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  # 如果未找到目标值，返回 -1

示例输入和输出​

假设我们有一个有序数组 arr = [1, 3, 5, 7, 9, 11, 13, 15]，我们需要查找目标值 target = 7。

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

输出：

目标值 7 的索引是: 3

二分搜索的步骤详解​

让我们通过一个具体的例子来理解二分搜索的每一步。

示例数组​

arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
  1. 初始范围：left = 0, right = 7（数组长度为 8）。
  2. 第一次迭代：
    • 计算中间索引：mid = (0 + 7) // 2 = 3。
    • 比较 arr[3] 和 target：7 == 7，找到目标值，返回索引 3。

如果目标值不在数组中，例如 target = 8，搜索过程如下：

  1. 初始范围：left = 0, right = 7。
  2. 第一次迭代：
    • mid = 3，arr[3] = 7 < 8，更新 left = mid + 1 = 4。
  3. 第二次迭代：
    • mid = (4 + 7) // 2 = 5，arr[5] = 11 > 8，更新 right = mid - 1 = 4。
  4. 第三次迭代：
    • mid = (4 + 4) // 2 = 4，arr[4] = 9 > 8，更新 right = mid - 1 = 3。
  5. 结束：left > right，返回 -1。

二分搜索的实际应用​

二分搜索在许多实际场景中都有广泛应用，例如：

  1. 查找有序列表中的元素：如电话簿、字典等。
  2. 数值计算：如在数学问题中寻找方程的根。
  3. 游戏开发：如在游戏中快速查找某个对象的位置。
  4. 数据库查询：如在有序索引中快速查找记录。
提示

二分搜索不仅适用于数组，还可以用于其他数据结构，如二叉搜索树（BST）。

总结​

二分搜索是一种高效的搜索算法，适用于有序数组。它的时间复杂度为 O(log n)，远优于线性搜索的 O(n)。通过不断缩小搜索范围，二分搜索能够快速定位目标值。

附加资源与练习​

  1. 练习：尝试在无序数组中使用二分搜索，观察结果并思考原因。
  2. 扩展阅读：学习如何在二叉搜索树中实现二分搜索。
  3. 挑战：编写一个递归版本的二分搜索算法。

通过掌握二分搜索，你将能够更高效地解决许多搜索问题。继续练习并尝试将其应用到实际项目中吧！