博客

python二分法实现实例

  • Post category:Python

下面是详细讲解“Python二分法实现实例”的完整攻略，包含两个示例说明。

二分法

二分法是一种常用的查找算法，也称为折半查找。的基本思想是将有序数组分成两部分，然后判断目标值在哪一部分中，再在该部分中继续查找，直到找到目标值或者确定目标值不存在为止。二分法的时间复杂度为O(log n)，适用于大规模数据的查找。

Python实现二分法

下面是一个示例代码，用于实现二分法：

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

这个代码定义了一个函数binary_search，用于在有序数组arr中查找目标值target。它使用while循环实现二分法，将数组分成左右两部分，并在每次迭代中判断目标值在哪一部分中。如果找到目标值，则返回其索引；否则，返回-1。

示例1：在有序数组中查找目标值

让我们使用上面的代码在有序数组中查找目标值。我们将以下代码：

arr = [1, 3, 5, 7, 9]
target = 5

result = binary_search(arr, target)

if result != -1:
    print('Target found at index', result)
else:
    print('Target not found')

这个代码使用binary_search函数在有序数组arr中查找目标值target。我们将arr和target作为参数传递给binary_search函数，并将结果存储在result变量中。如果找到目标值，则打印其索引；否则，打印“Target not found”。

输出结果为：

Target found at index 2

这表示目标值5在数组中的索引为2。

示例2：在旋转有序数组中查找目标值

让我们使用上面的代码在旋转有序数组中查找目标值。我们将以下代码：

arr = [4, 5, 6, 7, 0, 1, 2]
target = 0

result = binary_search(arr, target)

if result != -1:
    print('Target found at index', result)
else:
    print('Target not found')

这个代码使用binary_search函数在旋转有序数组arr中查找目标值target。我们将arr和target作为参数传递给binary_search函数，并将存储在result变量中。如果找到目标值，则打印其索引；否则，打印“Target not found”。

输出结果为：

Target found at index 4

这表示目标值0在旋转有序数组arr中的索引为4。

希望这些示例说明帮助你理解如何使用Python实现二分法。

Tags: ,