博客

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

  • Post category:Python

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不在数组中。

Tags: ,