Python 二分查找|极客教程

Python 二分查找

二分查找是一种高效的查找算法，也称为折半查找。它只适用于有序的序列，并且能够快速定位目标值的位置。本文将详细介绍 Python 中二分查找的实现方式及其应用场景。

二分查找的原理

二分查找的原理很简单，它通过将目标值与序列的中间值进行比较，从而缩小查找范围。具体步骤如下：

确定查找范围的起始位置 low 和结束位置 high，分别指向序列的第一个元素和最后一个元素。
在查找范围内计算中间位置 mid，并将其与目标值进行比较。
如果目标值等于中间值，则返回中间位置的索引值；否则根据比较结果更新 low 或 high。
重复以上步骤，直到找到目标值或者范围缩小到空集。

Python 实现二分查找

下面是一个基本的二分查找算法的 Python 实现：

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

在这个实现中，binary_search 函数接受一个有序序列 arr 和目标值 target，然后使用循环在查找范围内不断更新 low、high 和 mid，直到找到目标值或者范围缩小为空时返回 -1。

二分查找的应用场景

二分查找在很多场景下都能发挥作用，尤其是对于大型有序序列的查找问题。以下是一些常见的应用场景：

查找有序数组中的目标值：二分查找可以在有序数组中快速定位目标值的位置。
查找缺失的数字：可以通过二分查找在有序序列中查找缺失的数字。
查找旋转有序数组中的目标值：二分查找可以应用在旋转有序数组中查找目标值。
查找局部最小值：在某些特定问题中，可以使用二分查找找到局部最小值的位置。

示例

让我们通过一个示例来验证上面实现的二分查找算法。假设有一个有序数组 [1, 3, 5, 7, 9, 11, 13, 15]，现在要查找目标值 7 的位置：

arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
result = binary_search(arr, target)

print("目标值 7 的索引位置为：", result)

运行结果为：

目标值 7 的索引位置为： 3

可以看到，二分查找算法成功找到了目标值 7 在有序数组中的位置为索引 3。

总结

二分查找是一种高效的查找算法，可以在有序序列中快速定位目标值的位置。Python 提供了简洁而易读的语法，使得实现二分查找变得简单。通过本文的介绍，相信读者对 Python 中的二分查找有了更清晰的认识，并能够在实际开发中灵活运用。

Python 二分查找