博客

python二分法查找实例代码

  • Post category:Python

Python二分法查找实例代码

二分法查找是一种常用的查找算法，其基本思想是将有序数组分成两部分，然后判断目标在哪一部分中，再递归地在该部分中查找目标值。本攻略将介绍如何使用Python实现二分法查找的方法和代码实例。

二分法查找的原理

二分法查找的原理是将有序数组分成两部分，然后判断目标值在哪一部分中，递归地在该部分中查找目标值。具体步骤如下：

  1. 将有序数组分成两部分，取中间位置的数作为中间值。
  2. 如果中间值等于目标值，则返回中间值的下标。
  3. 如果中间值大于目标值，则在左半分继续查找。
  4. 如果中间值小于目标值，则在右半部分继续查找。
  5. 重复以上步骤，直到找到目标值或者数组被查完。

Python实现二分法查找

以下是使用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

在这个函数中，我们使用while循环来查找目标值。我们使用left和right两个指针来表示数组的左右边界，使用mid指针来表示数组的中间位置。我们在每次循环中计算mid的值，并判断mid位置的值是否等于目标值。如果mid位置的值等于目标值，则返回mid的下标。如果mid位置的值小于目标值，则在右半部分继续查找。如果mid位置的值大于目标值，则在左半部分继续查找。如果最终没有找到目标值，则返回-1。

以下是使用binary_search函数查找目标值的示例代码：

arr = [1, 3, 5, 7, 9]
target = 5
print(binary_search(arr, target))

在这个示例中，我们定义了一个有序数组arr和目标值target，并使用binary_search函数查找目标值的下。如果找到目标值，则输出其下标。如果没有找到目标值，则输出-1。

二分法查找的应用

二分法查找常用于查找有序数组中的元素。由于二分法查找的时间复杂度为O(log n)，因此它比线性查找更加高效。二分法查找还可以用于查找某个值的边界，例如查找某个值在有序数组中第一次出现的位置或最后一次出现的位置。

以下是使用二分法查找查找某个值在有序数组中第一次出现的位置的示例代码：

def binary_search_first(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] >= target:
            right = mid - 1
        else:
            left = mid + 1
    if left < len(arr) and arr[left] == target:
        return left
    else:
        return -1

在这个函数中，我们使用while循环来查找目标值。我们使用left和right两个指针来表示数组的左右边界，使用mid指针来表示数组的中间位置。我们在每次循环中计算mid的值，并判断mid位置的值是否大于等于目标值。如果mid位置的值大于等于目标值，则在左半部分继续查找。如果mid位置的值小于目标值，则在右半部分继续查找。如果最终找到目标值，则返回目标值第一次出现的位置。如果没有找到目标值，则返回-1以下是使用binary_search_first函数查找某个值在有序数组中第一次出现的位置的示例代码：

arr = [1, 2, 2, 3, 3, 3, 4, 5, 5]
target = 3
print(binary_search_first(arr, target))

在这个示例中，我们定义了一个有序数组arr和目标值target，并使用binary_search_first函数查找目标值在有序数组中第一次出现的位置。如果找到目标值，则输出其下标。如果没有找到目标值，则输出-1。

结论

本攻略中，介绍了二分法查找的原理和Python实现方法。我们使用示例代码演示了如何使用Python实现二分法查找，并介绍了二分法查找的应用场景。这些示例代码可以帮助读者更好地理解二分法查找的方法和应用场景。

Tags: ,