列表查找:从列表中查找指定元素:
- 输入:列表、待查找元素
- 输出:元素下标或为、未查找到元素
顺序查找:
- 从列表第一个元素开始,顺序进行搜索,直到找到为止
二分查找:
从有序列表的候选区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)
声明:1. 本站所有资源来源于用户上传和网络,因此不包含技术服务请大家谅解!如有侵权请邮件联系客服!
2. 本站不保证所提供下载的资源的准确性、安全性和完整性,资源仅供下载学习之用!如有链接无法下载、失效或广告,请联系客服处理!
3. 您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容资源!如用于商业或者非法用途,与本站无关,一切后果请用户自负!
2. 本站不保证所提供下载的资源的准确性、安全性和完整性,资源仅供下载学习之用!如有链接无法下载、失效或广告,请联系客服处理!
3. 您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容资源!如用于商业或者非法用途,与本站无关,一切后果请用户自负!