Python实现二分法

二分查找，也称为折半查找，是一种在有序数组中查找特定元素的搜索算法。它的工作原理是每次将待查找区间缩小一半，直到找到目标值或确定区间为空。以下是Python中实现二分查找的基本步骤：

def binary_search(arr, target):
    low = 0  # 区间开始下标
    high = len(arr) - 1  # 区间结束上标

    while low <= high:
        mid = (low + high) // 2  # 计算中间位置
        if arr[mid] == target:  # 如果中间值就是目标，返回索引
            return mid
        elif arr[mid] < target:  # 如果中间值小于目标，调整区间的下界到中间偏右一位
            low = mid + 1
        else:  # 如果中间值大于目标，调整区间的上界到中间偏左一位
            high = mid - 1

    # 如果遍历结束后仍未找到目标，返回-1表示未找到
    return -1

# 使用示例
arr = [1, 3, 5, 7, 9]
target = 5
result = binary_search(arr, target)
if result != -1:
    print(f"找到了，索引为 {result}")
else:
    print("没找到")

相关问题

python实现二分法

二分查找算法（Binary Search），也被称为折半搜索，是一种在有序数组中寻找特定元素的搜索算法。它的工作原理是每次将数组分成两部分，判断目标值在哪一部分，然后继续在这个部分内应用同样的过程，直到找到目标值或者确定其不存在于数组中。Python实现二分查找通常如下：

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    # 如果没找到目标值，返回-1表示不在数组中
    return -1

# 示例用法
arr = [1, 3, 5, 7, 9]
target = 5
result = binary_search(arr, target)
if result != -1:
    print(f"元素 {target} 在数组中的索引是 {result}")
else:
    print(f"{target} 不在数组中")

python实现二分法求根

二分法求根是一种简单有效的数值计算方法，可以用来寻找函数的零点。以下是Python实现二分法求根的示例代码：

def binary_search_root(f, a, b, tol=1e-6, max_iter=100):
    """
    使用二分法求解函数f在区间[a, b]上的根。
    :param f: 目标函数
    :param a: 区间左端点
    :param b: 区间右端点
    :param tol: 精度要求
    :param max_iter: 最大迭代次数
    :return: 根的近似值
    """
    fa, fb = f(a), f(b)
    if fa * fb > 0:
        raise ValueError("函数f在区间[a, b]上没有根。")
    for i in range(max_iter):
        c = (a + b) / 2
        fc = f(c)
        if abs(fc) < tol:
            return c
        if fa * fc < 0:
            b, fb = c, fc
        else:
            a, fa = c, fc
    raise ValueError("二分法迭代次数超过了最大值。")

其中，f是目标函数，a和b是区间的左右端点，tol是精度要求，max_iter是最大迭代次数。函数首先检查区间上是否存在根，然后使用for循环迭代求解。每次迭代，代码计算区间的中点c，然后根据函数值的符号将区间缩小。如果找到了满足精度要求的根，函数返回根的近似值。如果迭代次数超过了最大值，函数抛出异常。