Python二分查找算法详解

目前golang学习网上已经有很多关于文章的文章了，自己在初次阅读这些文章中，也见识到了很多学习思路；那么本文《Python二分查找实现方法详解》，也希望能帮助到大家，如果阅读完后真的对你学习文章有帮助，欢迎动动手指，评论留言并分享~

二分查找需要有序数组，因为1.有序性允许根据中间值判断目标位置，2.若数组无序无法确定搜索方向。其核心是每次将搜索区间减半，通过维护low、high和mid指针实现，比较mid元素与目标值调整搜索区间，直到找到目标或区间为空。迭代实现优于递归，因1.内存效率高，2.无递归深度限制，3.性能更稳定。变体包括查找首个/末个目标、下界/上界、旋转数组查找、二分答案等，拓展了应用场景。

Python实现二分查找，说白了，就是在一个已经排好序的列表里找某个特定元素。它的核心思想是每次都把搜索区间减半，效率非常高。

解决方案

实现二分查找，我们通常会用迭代的方式，因为它更直观，而且避免了递归深度的问题。你需要维护三个指针：low、high 和 mid。low 指向搜索区间的起始，high 指向结束，mid 则是中间点。每次比较 mid 位置的元素和目标值，然后根据比较结果调整 low 或 high，直到找到目标或者搜索区间为空。

def binary_search_iterative(arr, target):
    """
    使用迭代方式实现二分查找。
    :param arr: 必须是已排序的列表
    :param target: 要查找的目标值
    :return: 如果找到目标，返回其索引；否则返回 -1
    """
    low = 0
    high = len(arr) - 1

    while low <= high:
        # 避免潜在的整数溢出，虽然Python整数大小没有限制，
        # 但这是一个好习惯，尤其在其他语言中。
        mid = low + (high - low) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            # 目标在右半部分
            low = mid + 1
        else:
            # 目标在左半部分
            high = mid - 1

    # 循环结束，表示没有找到目标
    return -1

# 示例
# my_list = [1, 3, 5, 7, 9, 11, 13, 15]
# print(f"查找 9 的位置: {binary_search_iterative(my_list, 9)}")  # 输出 4
# print(f"查找 6 的位置: {binary_search_iterative(my_list, 6)}")  # 输出 -1

这段代码的核心逻辑就是那个 while low <= high 循环。每一次迭代，我们都把搜索范围缩小一半，直到找到目标或者范围变得无效（low > high）。

为什么二分查找需要有序数组？

这其实是二分查找最根本的限制，也是它能高效运作的基石。说白了，二分查找之所以能每次都“砍掉”一半的搜索空间，完全依赖于数组的有序性。

你想想看，当我们拿到中间元素 arr[mid] 时，如果它比我们要找的 target 小，我们能立刻确定 target（如果存在的话）一定在 mid 的右边。反之，如果 arr[mid] 比 target 大，那 target 就一定在 mid 的左边。这种判断之所以成立，就是因为数组是排好序的。如果数组是乱的，你根本没法根据 arr[mid] 和 target 的大小关系来判断 target 在哪边，因为右边可能有一个比 arr[mid] 小的数，左边也可能有一个比 arr[mid] 大的数。

所以，如果你的数据是无序的，想要用二分查找，就得先把它排好序。这个排序的过程本身就需要时间，比如用快速排序或归并排序，时间复杂度是 O(N log N)。而二分查找本身的复杂度是 O(log N)。这意味着，对于一次性查找，如果数据量大且无序，排序的开销可能会远大于查找的收益。但如果数据只排序一次，然后需要进行多次查找，那么二分查找的优势就非常明显了。

递归与迭代实现二分查找，哪个更优？

这两种实现方式各有千秋，但就Python而言，我个人更倾向于迭代实现。

迭代实现就像上面代码展示的那样，它通过一个 while 循环来不断调整 low 和 high 指针。它的优点很明显：

• 内存效率高： 不会产生额外的函数调用栈，因此在处理非常大的数据集时，不会有递归深度限制的问题（Python默认递归深度是1000）。
• 性能稳定： 每次迭代都是固定的操作，没有函数调用的额外开销。
• 易于理解和调试： 整个过程在一个函数内部完成，变量状态变化清晰。

# 迭代实现（已在解决方案中给出）
# def binary_search_iterative(arr, target):
#     low = 0
#     high = len(arr) - 1
#     while low <= high:
#         mid = low + (high - low) // 2
#         if arr[mid] == target: return mid
#         elif arr[mid] < target: low = mid + 1
#         else: high = mid - 1
#     return -1

递归实现则更具函数式编程的优雅感，它将问题分解为更小的子问题。

def binary_search_recursive(arr, target, low, high):
    """
    使用递归方式实现二分查找。
    :param arr: 已排序的列表
    :param target: 要查找的目标值
    :param low: 当前搜索区间的起始索引
    :param high: 当前搜索区间的结束索引
    :return: 如果找到目标，返回其索引；否则返回 -1
    """
    if low > high:
        return -1  # 搜索区间为空，未找到

    mid = low + (high - low) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        # 目标在右半部分，递归查找右子区间
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        # 目标在左半部分，递归查找左子区间
        return binary_search_recursive(arr, target, low, mid - 1)

# 示例调用
# my_list = [1, 3, 5, 7, 9, 11, 13, 15]
# print(f"递归查找 9 的位置: {binary_search_recursive(my_list, 9, 0, len(my_list) - 1)}")
# print(f"递归查找 6 的位置: {binary_search_recursive(my_list, 6, 0, len(my_list) - 1)}")

递归的缺点在于：

• 可能导致栈溢出： 对于非常大的列表，递归深度可能会超过Python的限制，抛出 RecursionError。
• 函数调用开销： 每次函数调用都会有额外的开销，理论上性能会比迭代略低（虽然对于O(log N)的算法，这点差异通常不明显）。

所以，除非你有特别的理由（比如觉得递归代码更“漂亮”或者在某些特定场景下更容易理解），否则我建议还是优先考虑迭代实现。它更稳健，更“工程化”。

二分查找在实际应用中还有哪些变体和优化？

二分查找虽然基本形式简单，但在实际工程中，它有很多灵活的变体，远不止“找一个数”这么简单。这些变体让它能解决一类非常有趣的问题。

• 查找第一个/最后一个出现的目标值： 当列表中存在重复元素时，我们可能需要找到某个目标值的第一个或最后一个出现的位置。这需要在找到 arr[mid] == target 后，不直接返回，而是继续向左（找第一个）或向右（找最后一个）搜索。

  • 例如，找第一个等于 target 的：当 arr[mid] == target 时，记录 mid 为一个可能的答案，然后继续在 [low, mid-1] 区间查找，看有没有更靠左的。
  • 找最后一个等于 target 的：当 arr[mid] == target 时，记录 mid 为一个可能的答案，然后继续在 [mid+1, high] 区间查找，看有没有更靠右的。

• 查找第一个大于等于/小于等于目标值的元素（即“下界”和“上界”）： 这在很多数据结构（比如平衡二叉搜索树、C++ STL中的 lower_bound 和 upper_bound）中非常常见。

  • 下界 (Lower Bound): 找到第一个大于或等于 target 的元素。如果所有元素都小于 target，则返回列表长度。
  • 上界 (Upper Bound): 找到第一个大于 target 的元素。如果所有元素都小于或等于 target，则返回列表长度。

• 在旋转排序数组中查找： 比如 [4, 5, 6, 7, 0, 1, 2] 这种数组，它原本是排序的，但被某个点“旋转”了。在这种数组中查找元素，需要先判断 mid 在哪一半（左半部分有序还是右半部分有序），然后根据 target 的值决定下一步搜索哪个区间。这比普通的二分查找复杂一些，但核心思想还是通过 mid 来缩小搜索范围。

• “二分答案” (Binary Search on Answer)： 这是一种非常巧妙的用法，当问题的答案在一个连续的区间内，并且满足某个单调性条件时，我们可以对答案本身进行二分查找。例如，求一个数的平方根（在一定精度内），或者在一些优化问题中（比如“最大化最小值”或“最小化最大值”）。这种情况下，二分查找不再是对数组索引进行，而是对答案的可能取值范围进行。你需要定义一个 check(x) 函数，判断 x 是否满足某个条件，并且这个条件是单调的。

• 优化 mid 的计算： 虽然在Python中 (low + high) // 2 很少会溢出，但在C++或Java等语言中，low + high 可能会导致整数溢出。因此，更安全的写法是 mid = low + (high - low) // 2。这个小细节在实际编程竞赛或对代码健壮性要求高的场景下是值得注意的。

这些变体和应用，让二分查找不仅仅是一个查找算法，更是一种解决问题的通用思路，特别是在处理有序数据或具有单调性质的问题时，它的效率和优雅性都非常突出。

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于文章的相关知识，也可关注golang学习网公众号。