二分查找算法

阅读量: 147 编辑

二分查找(Binary Search)是一种用于在有序数组(或列表)中查找特定元素的高效算法。

它通过重复将待查找范围划分为两半,并与中间元素进行比较,从而将查找范围迅速缩小。

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


# 测试二分查找算法
sorted_list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 11
result = binary_search(sorted_list, target)

if result != -1:
    print(f"元素 {target} 在索引 {result} 处找到")
else:
    print("元素不存在于列表中")

运行这段代码将输出:

元素 11 在索引 5 处找到

在这个示例中,binary_search() 函数接受一个有序数组和目标元素作为参数,并在数组中查找目标元素。

它使用 leftright 指针来跟踪查找范围的边界,然后根据中间元素与目标元素的比较来更新边界。循环继续进行,直到 left 大于 right,表示查找范围为空,或者找到目标元素,返回其索引。如果未找到目标元素,则返回 -1。

二分查找算法的时间复杂度为 O(log n),其中 n 是数组的大小。由于每次迭代将查找范围减半,因此它比线性查找更快速。二分查找要求数组必须是有序的。

爱码岛编程公众号
微信扫码关注
爱码岛编程小程序
微信扫码打开
苏ICP备13052010号
©2023 南京匠成信息科技有限公司