首页 / 算法 / 搜索算法----二分查找
搜索算法----二分查找
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了搜索算法----二分查找,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1734字,纯文字阅读大概需要3分钟。
内容图文
![搜索算法----二分查找](/upload/InfoBanner/zyjiaocheng/849/6822d9f5e22c4644ab770e2fc585d787.jpg)
所谓搜索就是在序列当中查找某一元素,这就叫做搜索,但是如果我们没有学习算法的知识的话,使用传统的查找方式就是从第一个元素到最后一个元素,除了传统的查抄方式之外,还有一个就是有个算法-------二分查找
二分查找就像我们查字典一样,先把字典分成两个部分,假如说我查找p字母,我将字典分成两半后看到的字母是M,因为字典是按顺序排列的,所以p字母是在m字母的后面,然后,我在将m字母后面的一半再分成两个部分,再看我当前页是否在p字母的前半部分还是右半部分,或者说正好就是p字母,按照这个思路在进行依次向下分。
这样查找方式可以提高我们一半的效率。
二分查找优点是比较次数少,查找速度快,平均性能好,其缺点是要求查找是有序表且插入删除困难·,因此,二分查找方法适用于不经常变动而查找频繁的有序数列。
二分查找的缺点也是二分查找要满足以下条件,也就是就是我们的数列必须是按照顺序排列的
二分查找可以分两种方式进行书写,一种是递归方式,另一种是非递归方式。
python的递归方式:
ef binary_search(alist,item):
n = len(alist) #计算alist的长度
if n>0:
mid = n//2
if item == alist[mid]:
return True
elif item<alist[mid]:
return binary_search(alist[:mid],item) #进行递归操作
else:
return binary_search(alist[mid+1:],item) #因为列表中包括前面但是不包括后面,因此mid+1
return False
if __name__ == "__main__":
li = [17,20,26,31,44,54,55,77,93]
print(binary_search(li,55))
python非递归方式:
#非递归方式
def binary_search(alist,item):
n = len(alist)
first = 0
last = n-1
while first <= last:
mid = (first+last) // 2
if item == alist[mid]:
return True
elif item < alist[mid]:
last = mid -1
else:
first = mid+1
return False
if __name__ == "__main__":
li = [17,20,26,31,44,54,55,77,93]
print(binary_search(li,55))
内容总结
以上是互联网集市为您收集整理的搜索算法----二分查找全部内容,希望文章能够帮你解决搜索算法----二分查找所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。