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

公众号新增加了一个栏目,就是每天给大家解答一道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

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

更多题目:

10、说说Python可变与不可变数据类型?

11、说说Python模块主要分哪三类?

12、列举Python中的标准异常类?

13、Python中深拷贝与浅拷贝的区别?

14、Python中迭代器和生成器的区别?

15、Python可迭代对象怎么获取迭代器?

16、你了解什么是 Python 之禅么?

17、说说Python字典以及基本操作?

18、说说Python有几种字符串格式化?

19、说说Python多线程与多进程的区别?

20、说说HTTP常见响应状态码?

21、Python 单引号、双引号、三引号区别?

22、说说Python中猴子补丁是什么?

23、说说Python中的垃圾回收机制?

24、Python中有几种交换两个变量的值?

25、说说Python中的6种位运算符?

26、说说Python中的类型转换有哪些?

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

本文分享自微信公众号 - 程序IT圈(DeveloperIT)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

评论

暂无评论