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

标签: 面试  twitter  python  软件测试  glassfish

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

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

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中的类型转换有哪些?

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

版权声明:本文为itcodexy原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/itcodexy/article/details/109573679

智能推荐

Qt 之 Query Model Example 解析

总体概括 Query Model Example主要演示了怎么使用QSqlQueryModel这个数据库查询模型类。其中包括创建普通的数据库查询模型、可编辑的数据库查询模型和自定义的数据库查询模型。普通(默认)的数据库查询模型是只读的(不可再模型中编辑数据,模型只通过视图展示数据);可编辑的数据库查询模型重写了QSqlQueryModel的flags()方法和setData()方法;自定义的数据库...

Flutter:Scaffold.of() called with a context that does not contain a Scaffold.

Flutter:Scaffold.of() called with a context that does not contain a Scaffold. 当我第一次点击按钮想要弹出底部消息时出现了如下错误 当BuildContext在Scaffold之前时,调用Scaffold.of(context)会报错。这时可以通过Builder Widget来解决,代码如下:...

【机器学习基础】线性回归

                                                        &nbs...

08-Vue实现书籍购物车案例

书籍购物车案例 index.html main.js style.css 1.内容讲解 写一个table和thead,tbody中每一个tr都用来遍历data变量中的books列表。 结果如下: 在thead中加上购买数量和操作,并在对应的tbody中加入对应的按钮。结果如下: 为每个+和-按钮添加事件,将index作为参数传入,并判断当数量为1时,按钮-不可点击。 结果如下: 为每个移除按钮添加...

堆排序

堆排序就是利用堆进行排序的方法,基本思想是,将代排序列构造成一个大根堆,此时整个序列的最大值就是堆顶的根节点。将它与堆数组的末尾元素交换,此时末尾元素就是最大值,移除末尾元素,然后将剩余n-1个元素重新构造成一个大根堆,堆顶元素为次大元素,再次与末尾元素交换,再移除,如此反复进行,便得到一个有序序列。 (大根堆为每一个父节点都大于两个子节点的堆) 上面思想的实现还要解决两个问题: 1.如何由一个无...

猜你喜欢

基础知识(变量类型和计算)

一、值类型 常见的有:number、string、Boolean、undefined、Symbol 二、引用类型 常用的有:object、Array、null(指针指向为空)、function 两者的区别: 值类型暂用空间小,所以存放在栈中,赋值时互不干扰,所以b还是100 引用类型暂用空间大,所以存放在堆中,赋值的时候b是引用了和a一样的内存地址,所以a改变了b也跟着改变,b和a相等 如图: 值...

Codeforces 1342 C. Yet Another Counting Problem(找规律)

题意: [l,r][l,r][l,r] 范围内多少个数满足 (x%b)%a!=(x%a)%b(x \% b) \% a != (x \% a) \% b(x%b)%a!=(x%a)%b。 一般这种题没什么思路就打表找一下规律。 7 8 9 10 11 12 13 14 15 16 17 18 19 20 28 29 30 31 32 33 34 35 36 37 38 39 40 41 49 50...

[笔记]飞浆PaddlePaddle-百度架构师手把手带你零基础实践深度学习-21日学习打卡(Day 3)

[笔记]飞浆PaddlePaddle-百度架构师手把手带你零基础实践深度学习-21日学习打卡(Day 3) (Credit: https://gitee.com/paddlepaddle/Paddle/raw/develop/doc/imgs/logo.png) MNIST数据集 MNIST数据集可以认为是学习机器学习的“hello world”。最早出现在1998年LeC...

哈希数据结构和代码实现

主要结构体: 实现插入、删除、查找、扩容、冲突解决等接口,用于理解哈希这种数据结构 完整代码参见github: https://github.com/jinxiang1224/cpp/tree/master/DataStruct_Algorithm/hash...