Python真题案例之二分法查找详解

目录

• 写在前面的话
• 问题描述
• 原理分析
• 1.实现步骤
• 2.图解
• 参考代码

写在前面的话

学了python一些基础知识之后,相信大家对Python使用方法有了一定的感悟,想要追求深层次的东西还要细细的学、慢慢的学。Python基础教程更新到今天语法基础算是完了,本专栏后续会对面向对象模块更新。在进行面向对象更新之前呢会有一步小插曲就是Python 百炼成钢系列http://www.cppcns.com。主要的作用呢就是使用Python刷一刷算法题，使自己的基础更加稳固。在更新期间收到了广大小伙伴的喜爱,博主的知识水平也有所提升。下面呢咱们进入正题讲解今天咱们要学习的二分查找法。

问题描述

在学习一门语言的时候,咱们做的最多的一件事就是对数据进行增删改查,而对于增删改查操作中最常做的就是查,因为一个软件主要的作用就是对亲爱的用户进行信息展示,只有少部分管理员或者拥有权限的用户才可以操作数据。比如在链表、数组中查找东西,咱们需要从头开始遍历,挨个检索。数据量庞大编程客栈的时候会很令人头疼。今天介绍的二分法查找(或称折半查找) 主要是针对有序数列（也就是说数据要先排序）。然后每次取中值进行比较,依次折半缩小查找范围。

原理分析

1.实现步骤

• 1）确定该区间的中间位置K,在数组两边加上区间左右边界l,r
• 2）将查找的值T与array[k]比较。若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。

区域确定如下：

• 每一次查找与中间值比较，判断是否查找成功，不成功当前查找区间将缩小一半。 视情况重新定左右边界与中间索引k
• 时间复杂度为:O(log2n)。

2.图解

图片源于网络

参考代码

这里在写代码的时候对比了系统内置查找关键字in与二分法查找的运行效果 打印结果如下：

由此可见Python底层的查找算法还是超级快的。使用起来也很方便

二分查找在本次实验中输在了需要对列表进行排序上

对于有序量大的数据就可以体现出来二分查找的优势了

import time,math,random

#计时器（使用的是函数装饰器前面说函数的时候提到过）
def timeT(func):
    def wapper(*s):
        start=time.perf_counter()
        judge=func(*s)
        end=time.perf_counter()
        return judge,start-end
    return wapper
# 使用内置查找方法
@timeT
defPnbKqzgIw serch1(lists,e):
    return e in lists

# 二分法
@ timeT
def serch2(lists,e):
    flag=False
    lists=sorted(lists)
    # print(lists)
    # 左游标
    lo=0
    # 右游标
    ma=len(lists)-1
    # 中间位置
    mid=len(lists)//2
    # 没有在列表内
    if lists[ma]<e:
        return False
    if lists[lo]>e:
        return False
    # 依次缩小左右游标，直到lo编程客栈>ma
    while lo<=ma:
        if lists[mid]>e:
            ma=mid
            mid=(lo+ma)//2
        elif lists[mid]<e:
            lo=mid
            mid=(lo+ma)//2
        else:
        	#标记位,True代表查到了
            flag=True
            break
    return flag


def main():
	#生成一个含有10000个元素的列表
    numarr=[x for x in range(10000)]
    #打乱列表顺序
    random.shuffle(numarr)
    print(*serch1(numarr,23))
    print(*serch2(numarr,223))
    print(223 in numarr)
    # print(编程客栈numarr)

if __name__=="__main__":
    main()  

到此这篇关于Python真题案例之二分法查找详解的文章就介绍到这了,更多相关Python 二分法查找内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！