百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 技术分类 > 正文

如何用Python实现二分搜索算法(python二分法查找代码)

ztj100 2025-04-11 09:51 71 浏览 0 评论

如何用Python实现二分搜索算法

二分搜索(Binary Search)是一种高效的查找算法,适用于在有序数组中快速定位目标值。其核心思想是通过不断缩小搜索范围,每次将问题规模减半,时间复杂度为 (O(log n))。以下是逐步讲解实现过程:

一、二分搜索的原理

1. 核心思想

  • 前提条件:数组必须是有序的(升序或降序,通常默认升序)。
  • 步骤

(1)确定搜索范围:初始范围为整个数组的起始索引 low 和结束索引 high。

(2)计算中间索引:mid = (low + high) // 2。

(3)比较中间元素: 如果 arr[mid] == target,返回 mid。 如果 arr[mid] < target low='mid' 1 arrmid> target,目标在左半部分,调整 high = mid - 1。

(4)重复步骤,直到找到目标或搜索范围无效(low > high)。

2. 示例演示

以数组 [1, 3, 5, 7, 9] 为例,查找目标 5:

  1. 初始范围:low = 0, high = 4。
  2. 第一次计算:mid = (0+4)//2 = 2,arr[2]=5,直接返回 2。

二、实现步骤

1. 确定搜索范围

  • 初始 low = 0,high = len(arr)-1。

2. 循环条件

  • 当 low <= high 时继续循环,否则说明未找到目标。

3. 计算中间索引

  • mid = (low + high) // 2(注意:避免整数溢出,但 Python 中无需担心)。

4. 调整搜索范围

  • 根据 arr[mid] 与目标值的比较结果,更新 low 或 high。

三、Python代码实现

3.1 迭代版本(推荐)

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        mid_val = arr[mid]
        
        if mid_val == target:
            return mid  # 找到目标,返回索引
        elif mid_val < target:
            low = mid + 1  # 目标在右半部分
        else:
            high = mid - 1  # 目标在左半部分
    return -1  # 未找到,返回-1

# 测试
test_list = [1, 3, 5, 7, 9]
print(binary_search(test_list, 5))   # 输出:2
print(binary_search(test_list, 2))   # 输出:-1

3.2 代码解释

  1. 初始化范围:low 和 high 分别指向数组的首尾。
  2. 循环条件:while low <= high 确保范围有效。
  3. 中间索引计算:mid = (low + high) // 2(向下取整)。
  4. 比较逻辑: 若 arr[mid] 等于目标,直接返回 mid。 若 arr[mid] 小于目标,目标在右半部分,因此 low = mid + 1。 反之,high = mid - 1。
  5. 未找到时返回-1:循环结束仍未找到,说明数组中无该元素。

3.3 递归版本(可选)

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

# 调用示例
test_list = [1, 3, 5, 7, 9]
print(binary_search_recursive(test_list, 5, 0, len(test_list)-1))  # 输出:2

四、测试与验证

4.1 正常测试

test_list = [2, 4, 6, 8, 10]
print(binary_search(test_list, 6))  # 输出:2
print(binary_search(test_list, 5))  # 输出:-1

4.2 边界测试

  • 空数组:binary_search([], 5) → 返回 -1。
  • 单元素数组:binary_search([5], 5) → 返回 0。
  • 目标在首/尾元素

(1)binary_search([1,2,3], 1) → 0

(2)binary_search([1,2,3], 3) → 2

五、优化与注意事项

5.1 处理重复元素

若数组中有重复值,二分搜索可能返回任意一个匹配的索引。若需找到第一个出现的位置最后一个位置,需调整条件:

  • 第一个出现的位置
while low <= high:
    mid = (low + high) // 2
    if arr[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
if low < len(arr) and arr[low] == target:
    return low
else:
    return -1

5.2 避免整数溢出(理论场景)

在某些语言(如 C++、Java)中,low + high 可能溢出,可用 mid = low + (high - low) // 2 替代。

六、总结步骤

  1. 确保数组有序:二分搜索的前提是数组必须有序。
  2. 初始化搜索范围:low 和 high 分别为数组首尾索引。
  3. 循环缩小范围:通过比较中间元素调整 low 或 high。
  4. 处理边界条件:确保循环终止条件正确(low <= high)。

七、练习题

  1. 降序数组的二分搜索:修改代码,使算法能在降序数组中正确查找目标。
  2. 查找第一个大于等于目标的元素
def find_first_ge(arr, target):
    low, high = 0, len(arr)-1
    res = -1
    while low <= high: mid='(low' high 2 if arrmid>= target:
            res = mid
            high = mid - 1
        else:
            low = mid + 1
    return res
  1. 实现递归版本的边界测试:验证递归函数在空数组、单元素等场景的表现。

通过以上步骤,可以逐步掌握二分搜索的实现逻辑,并理解其高效性和适用场景。

相关推荐

其实TensorFlow真的很水无非就这30篇熬夜练

好的!以下是TensorFlow需要掌握的核心内容,用列表形式呈现,简洁清晰(含表情符号,<300字):1.基础概念与环境TensorFlow架构(计算图、会话->EagerE...

交叉验证和超参数调整:如何优化你的机器学习模型

准确预测Fitbit的睡眠得分在本文的前两部分中,我获取了Fitbit的睡眠数据并对其进行预处理,将这些数据分为训练集、验证集和测试集,除此之外,我还训练了三种不同的机器学习模型并比较了它们的性能。在...

机器学习交叉验证全指南:原理、类型与实战技巧

机器学习模型常常需要大量数据,但它们如何与实时新数据协同工作也同样关键。交叉验证是一种通过将数据集分成若干部分、在部分数据上训练模型、在其余数据上测试模型的方法,用来检验模型的表现。这有助于发现过拟合...

深度学习中的类别激活热图可视化

作者:ValentinaAlto编译:ronghuaiyang导读使用Keras实现图像分类中的激活热图的可视化,帮助更有针对性...

超强,必会的机器学习评估指标

大侠幸会,在下全网同名[算法金]0基础转AI上岸,多个算法赛Top[日更万日,让更多人享受智能乐趣]构建机器学习模型的关键步骤是检查其性能,这是通过使用验证指标来完成的。选择正确的验证指...

机器学习入门教程-第六课:监督学习与非监督学习

1.回顾与引入上节课我们谈到了机器学习的一些实战技巧,比如如何处理数据、选择模型以及调整参数。今天,我们将更深入地探讨机器学习的两大类:监督学习和非监督学习。2.监督学习监督学习就像是有老师的教学...

Python教程(三十八):机器学习基础

...

Python 模型部署不用愁!容器化实战,5 分钟搞定环境配置

你是不是也遇到过这种糟心事:花了好几天训练出的Python模型,在自己电脑上跑得顺顺当当,一放到服务器就各种报错。要么是Python版本不对,要么是依赖库冲突,折腾半天还是用不了。别再喊“我...

超全面讲透一个算法模型,高斯核!!

...

神经网络与传统统计方法的简单对比

传统的统计方法如...

AI 基础知识从0.1到0.2——用“房价预测”入门机器学习全流程

...

自回归滞后模型进行多变量时间序列预测

下图显示了关于不同类型葡萄酒销量的月度多元时间序列。每种葡萄酒类型都是时间序列中的一个变量。假设要预测其中一个变量。比如,sparklingwine。如何建立一个模型来进行预测呢?一种常见的方...

苹果AI策略:慢哲学——科技行业的“长期主义”试金石

苹果AI策略的深度原创分析,结合技术伦理、商业逻辑与行业博弈,揭示其“慢哲学”背后的战略智慧:一、反常之举:AI狂潮中的“逆行者”当科技巨头深陷AI军备竞赛,苹果的克制显得格格不入:功能延期:App...

时间序列预测全攻略,6大模型代码实操

如果你对数据分析感兴趣,希望学习更多的方法论,希望听听经验分享,欢迎移步宝藏公众号...

AI 基础知识从 0.4 到 0.5—— 计算机视觉之光 CNN

...

取消回复欢迎 发表评论: