Python二分法查找算法实现方法【递归与非递归】

二分法查找算法是一种高效的查找算法，它的基本思想将有序数组分成两部分，然后判断目标值在哪一部分，再递归地在该部分中查找目值。本文将介绍Python中二分法查找算法的实现方法，包括递归和非递归两种方式。

二分法查找法实现方法

递归实现

递归实现二分法查找算法的基本思想是将有序数组分成两部分然后判断目标值在哪一部分，再递归地在该部分中查找目标值。具体实现方法如下：

def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search_recursive(arr, target, low, mid-1)
    else:
        return binary_search_recursive(arr, target, mid+1, high)

其中，arr为有序数组，target为目标值，low为数组的起始下标，high为数组的结束下标。如果目标值在数组，则返回目标值的下标；否则返回-1。

非递归实现

非递归实现二分法查找算法的基本思想是将有序数组分成两部分，然后判断目标值在哪一部分，再环地在该部分中查找目标值。具体实现如下：

def binary_search_iterative(arr, target):
    low, high = 0, len(arr)-1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            high = mid - 1
        else:
            low = mid + 1
    return -1

其中，arr为有序数组，target为目标值。标值在数组中，则返回目标值的下标；否则返回-1。

示例说明

示例1

假设有一个有序数组arr=[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]，需要查找目标值target11的下标可以使用递归实现的二分法查找算法，代码如下：

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 11
result = binary_search_recursive(arr, target, 0, len(arr)-1)
if result != -1:
    print("目标值在数组中的下标为：", result)
else:
    print("目标值不在数组中")

结果为：

目标值在数组中的下标为： 5

从输出结果可以看出，目标值11在数组中的下标为5。

示例2

假设有一个有序数组arr2, 4, 6, 8, 10, 12, 14, 16, 18, 20]，需要查找目标值target5的下标。可以使用非递归实现的二分法查找算法，代码如下：

arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
target = 5
result = binary_search_iterative(arr, target)
if result != -1:
    print("目标值在数组中的下标为：", result)
else:
    print("目标值不在数组中")

输出结果为：

目标值不在数组中

从输出结果可以看，目标值5不在数组中。

总结

本文介绍了Python中二分法查找算法的实现方法，包括递归和非递归两种方式。递归实现的二分法查找算法的基本思想是将有序数组分成两部分然后判断目标值在哪一部分，再递归地在该部分中查找目标值；非递归实现的二分法查找算法的基本思想是将有序数组分成两部分，然后判断目标值在哪一部分，再环地在该部分中查找目标值。在实际应用中，可以根据具体情况选择适合的实现方式。