Python二分法

CJHRL • 2025-04-28 13:17 • 编程

本文将详细介绍Python中的二分法的实现方法及其应用场景。

一、二分法简介

二分法，又叫二分查找法，是一种在有序数组中查找目标值的算法，其基本思想是将目标值与有序数组的中间值进行比较，根据比较的结果可以确定目标值位于数组的哪一部分。通过不断缩小查找范围，最终找到目标值或者确定不存在。

在Python中，二分法是一种高效的算法，运用广泛。例如在图像处理、数据分析、数值计算等领域都有着广泛的应用。

二、Python实现二分法

下面是Python实现二分法查找的模板代码：

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

二分法的关键在于将搜索范围不断缩小，这里通过left和right两个指针来完成。在每次循环中，计算出中间值mid，通过与目标值的比较来确定目标值所在的区间，并继续缩小区间，直至找到目标值。

三、二分法应用场景

二分法可以解决许多实际问题，下面介绍几个常见的应用场景。

1、寻找数值的峰值

在一个数组中，峰值指的是一个数既大于它左侧的数，也大于它右侧的数。使用二分法查找数值的峰值：

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

2、寻找有序数组中的目标值范围

在一个有序数组中，寻找目标值的范围可以使用二分法查找左右两个边界。

def search_range(nums, target):
    left, right = 0, len(nums) - 1
    left_bound, right_bound = -1, -1
    # 找左边界
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            right = mid - 1
            left_bound = mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    # 找右边界
    left, right = left_bound, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            left = mid + 1
            right_bound = mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return [left_bound, right_bound]

3、寻找旋转排序数组中的目标值

在一个旋转的有序数组中，寻找目标值可以使用二分法查找。

def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:  # 左半边有序
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # 右半边有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

四、总结

本文主要介绍了Python中的二分法，包括二分法的概念、Python实现二分法的代码模板，以及二分法的应用场景。从数值峰值的查找到目标值范围的寻找，再到旋转排序数组的查找，二分法无处不在，运用广泛。掌握了二分法的基本思想和代码实现，对于Python编程工程师来说是至关重要的。

原创文章，作者：CJHRL，如若转载，请注明出处：https://www.506064.com/n/374815.html