Python中实现二分查找的2种方法？-白红宇的个人博客

Python中实现二分查找的2种方法？

发布日期：2021-06-29 18:23:27 浏览次数：2 分类：技术文章

本文共 1390 字，大约阅读时间需要 4 分钟。

640?wx_fmt=gif

公众号新增加了一个栏目，就是每天给大家解答一道Python常见的面试题，反正每天不贪多，一天一题，正好合适，只希望这个面试栏目，给那些正在准备面试的同学，提供一点点帮助！

小猿会从最基础的面试题开始，每天一题。如果参考答案不够好，或者有错误的话，麻烦大家可以在留言区给出自己的意见和讨论，大家是要一起学习的。

废话不多说，开始今天的题目：

问：Python中实现二分查找的2种方法？

答：在Python实现二分查找法有两种方法，分别用循环和递归方式。

二分查找法：搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。注意如果要想使用二分查找，前提必须是元素有序排列。

640?wx_fmt=png

下面分别来说说这两种方式:

1、循环方式

def binary_search_2(alist,item):

"""二分查找---循环版本"""

n = len(alist)

first = 0

last = n-1

while first <= last:

mid = (first + last)//2

if alist[mid] ==item:

return True

elif item < alist[mid]:

last = mid - 1

else:

first = mid + 1

return False

if __name__ == "__main__":

a = [1,5,6,10,11,13,18,37,99]

sorted_list_21 = binary_search_2(a, 18)

print(sorted_list_21) //True

sorted_list_22 = binary_search_2(a, 77)

print(sorted_list_22) //False

2、递归方式

def binary_search(alist,item):

"""二分查找---递归实现"""

n = len(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)

else :

return False #失败

if __name__ == "__main__":

a = [1,5,6,10,11,13,18,37,99]

# print(a)

sorted_list_11 = binary_search(a,37)

print(sorted_list_11)//True

sorted_list_12= binary_search(a, 88)

print(sorted_list_12)//False

如果对于参考答案有不认同的，大家可以在评论区指出和补充，欢迎留言！

更多题目：

关注小猿公众号，每天学习一道题

640?wx_fmt=jpeg

转载地址：https://cxydev.blog.csdn.net/article/details/102480450 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：你知道吗？计算机界也有诺贝尔奖！

下一篇：MacOS Catalina终于来了！升级前先来看看有哪些亮点？

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章