ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 应用开发 > Python > 如何在 Python 中实现二分查找？

如何在 Python 中实现二分查找？

原创 Python 作者：mingtian66 时间：2024-11-10 12:54:48 0 删除 编辑

在 Python 中，可以通过递归或迭代的方式来实现二分查找。二分查找的前提是数组必须是有序的，它通过不断将查找范围缩小一半，来快速找到目标值的索引。
1. 递归实现

def binary_search_recursive(arr, target, left, right):
    # 基础情况：如果左指针超过右指针，表示未找到目标值
    if left > right:
        return -1
    
    # 计算中间索引
    mid = (left + right) // 2
    
    # 检查中间元素是否为目标值
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        # 目标值在右半部分
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        # 目标值在左半部分
        return binary_search_recursive(arr, target, left, mid - 1)

使用示例：

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
result = binary_search_recursive(arr, target, 0, len(arr) - 1)
print(result)  # 输出：4（目标值5的索引）

2. 迭代实现

def binary_search_iterative(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

使用示例：

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
result = binary_search_iterative(arr, target)
print(result)  # 输出：4（目标值5的索引）

来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/70040412/viewspace-3048244/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： Python 如何实现快速排序和归并排序？
下一篇： Java 中如何实现延迟初始化？
请登录后发表评论 登录
全部评论
mingtian66

注册时间：2024-08-07

  • 博文量
    589
  • 访问量
    603014

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593