跳到主要内容

用Python实现一个二分查找的函数?

参考答案:

二分查找(Binary Search)是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是目标值,则搜索过程结束;如果目标值大于或小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

以下是一个用Python实现的二分查找函数:

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

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

        # 如果 mid 元素 < x,忽略左半部分
        if arr[mid] < x:
            low = mid + 1

        # 如果 mid 元素 > x,忽略右半部分
        elif arr[mid] > x:
            high = mid - 1

        # mid 元素 == x,返回 mid
        else:
            return mid

    # x 不存在于 arr 中
    return -1

# 测试数组
arr = [2, 3, 4, 10, 40]
x = 10

# 函数调用
result = binary_search(arr, x)

if result != -1:
    print("元素在数组中的索引为", str(result))
else:
    print("元素不在数组中")

在这个函数中,arr 是要进行搜索的有序数组,x 是要查找的元素。如果元素在数组中,函数将返回元素的索引;如果元素不在数组中,函数将返回 -1。