公众号新增加了一个栏目，就是每天给大家解答一道Python常见的面试题，反正每天不贪多，一天一题，正好合适，只希望这个面试栏目，给那些正在准备面试的同学，提供一点点帮助！
小猿会从最基础的面试题开始，每天一题。如果参考答案不够好，或者有错误的话，麻烦大家可以在留言区给出自己的意见和讨论，大家是要一起学习的 。
废话不多说，开始今天的题目：
问：Python中实现二分查找的2种方法？
答：在Python实现二分查找法有两种方法，分别用循环和递归方式。
二分查找法：搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。注意如果要想使用二分查找，前提必须是元素有序排列 。
下面分别来说说这两种方式:
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 Falseif __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
如果对于参考答案有不认同的，大家可以在评论区指出和补充，欢迎留言！
更多题目：
关注小猿公众号，每天学习一道题
本文分享自微信公众号 - 程序IT圈（DeveloperIT）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
