Python列表查找 顺序查找 二分查找

鳄鱼君

发表文章数:523

Vieu四代商业主题

高扩展、安全、稳定、响应式布局多功能模板。

¥69 现在购买
首页 » Python教程 » Python列表查找 顺序查找 二分查找

列表查找:从列表中查找指定元素:

  1. 输入:列表、待查找元素
  2. 输出:元素下标或为、未查找到元素

顺序查找

  1. 从列表第一个元素开始,顺序进行搜索,直到找到为止

二分查找

有序列表的候选区data[0:n]开始,通过对待查找的值与候选值区中间值的比较,可以使候选区减少一半。

二分查找

假设现在有1-9位数,我想找到3。定义两个变量low和high,low为开始的下标,high为结束的下标。每次取中间的下标mid,就是(low+high)÷2。

 1    2    3    4    5    6    7    8    9
low                mid                  high 
 1    2    3    4    5    6    7    8    9
low  mid       high
              
 1    2    3    4    5    6    7    8    9
          low  high             
          mid

mid下标为5,3在mid左边,没有找到3,接着将high的下标移动到4的位置,即mid-1的位置,再次更新mid=(low+high)÷2的位置,即2的下标,这次3在mid的右边,将low的下标+1,即2位置,再计算mid的值,就找到了3。

按照以上的分析,编写代码,之前先搞一个计时的函数当做装饰器,因为我们后面都会用到:

import time
def cal_time(func):
    def wrapper(*args,**kwargs):
        start_time=time.time()
        x=func(*args,**kwargs)
        end_time=time.time()
        print('time cost:%s,%s'% (func.__name__,str(end_time-start_time)))
        return x
    return wrapper

二分查找代码参考:

@cal_time
def bin_search(data_set,val):
    low=0
    high=len(data_set)-1
    # low=high的时候有一个数
    while low<=high:
        mid=(low+high)//2
        if data_set[mid]==val: # 目标值等于mid
            return mid # 返回下标
        elif data_set[mid]<val: #目标值大于mid,即目标值在mid右边
            low=mid+1
        else:#目标值小于mid,即目标值在mid左边
            high=mid-1
    return
data=list(range(100000)) # 有序列表
bin_search(data,123)

未经允许不得转载:作者:鳄鱼君, 转载或复制请以 超链接形式 并注明出处 鳄鱼君
原文地址:《Python列表查找 顺序查找 二分查找》 发布于2020-06-26

分享到:
赞(0) 赏杯咖啡

评论 抢沙发

5 + 1 =


文章对你有帮助可赏作者一杯咖啡

支付宝扫一扫打赏

微信扫一扫打赏

Vieu4.6主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
切换注册

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录
切换登录

注册