Pythonic版二分查找实现过程原理解析
更新时间:2020年8月12日 09:13 点击:1978
前提:升序数组,待查元素在数组中。
二分查找:就是一个递归函数c。待查元素a,当前数组中位数b,如果b=a则返回b的索引,b>a则在b左侧的子数组中调用函数c,否则在b右侧子数组中调用函数c。
第一次思考,按着上面的思路编程后的结果:
def binary_search(index, a, value): if a[(len(a) - 1) // 2] == value: return index + (len(a) - 1) // 2 elif a[(len(a) - 1) // 2] < value: return binary_search(index + (len(a) - 1) // 2 + 1, a[(len(a) - 1) // 2 + 1:], value) else: return binary_search(index, a[0:(len(a) - 1) // 2 + 1], value)
第二次思考,简化中位数计算逻辑:
def binary_search(index, a, value): if a[len(a) // 2] == value: return index + len(a) // 2 elif a[len(a) // 2] < value: return binary_search(index + len(a) // 2, a[len(a) // 2:], value) else: return binary_search(index, a[0:len(a) // 2], value)
第三次思考,去掉return,改为lambda形式:
binary_search = lambda index,a,value: index + len(a) // 2 if a[len(a) // 2] == value else binary_search(index + len(a) // 2, a[len(a) // 2:], value) if a[len(a) // 2] < value else binary_search(index, a[0:len(a) // 2], value)
以上就是二分查找变为“一行代码”版的过程。
运行测试:
if __name__ == '__main__': a = [1, 2, 33, 43, 52, 66, 88, 99, 111, 120] print(f"Target index: {binary_search(0, a, value=33)}")
结果如下:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持猪先飞。
上一篇: 如何用python免费看美剧
相关文章
- 这篇文章主要介绍了python如何用moviepy对视频进行简单的处理,帮助大家更好的利用python处理视频,感兴趣的朋友可以了解下...2021-03-11
从Pytorch模型pth文件中读取参数成numpy矩阵的操作
这篇文章主要介绍了从Pytorch模型pth文件中读取参数成numpy矩阵的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-04- 这篇文章主要介绍了计算Python Numpy向量之间的欧氏距离实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-05-23
- 二分查找是一种在已经过排序的数组中搜索指定元素用的算法,这里我们就来看一下Ruby实现二分搜索(二分查找)算法的简单示例:...2020-06-30
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了jQuery实现查找最近父节点的方法,涉及jQuery针对元素节点操作的相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2016-06-24
- 这篇文章主要介绍了Python pymysql模块安装并操作过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-10-13
- 这篇文章主要介绍了C++实现的O(n)复杂度内查找第K大数算法,结合实例形式分析了算法的原理以及具体实现方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了聊聊.py和.ipynb的一些小知识,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-24
- 这篇文章主要介绍了python系统指定文件的查找只输出目录下所有文件及文件夹,本文给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下...2020-04-22
- 今天小编就为大家分享一篇Python-numpy实现灰度图像的分块和合并方式,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-27
Python编程OpenCV和Numpy图像处理库实现图片去水印
这篇文章主要介绍了Python编程中如何实现图片去水印本文采用了OpenCV和Numpy的图像处理的方法来实现,文中附含详细示例代码,有需要的朋友可以借鉴参考下...2021-09-26- 在本篇内容里小编给大家整理了关于python中二分查找法的实现方法,有需要的朋友们可以学习下。...2020-12-07
- 这篇文章主要介绍了引用numpy出错 解决方法的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了numpy的squeeze函数使用方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-22
- 这篇文章主要介绍了python3 读取python2的npy文件操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-27
- 这篇文章主要介绍了python numpy实现rolling滚动案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-06-08
- Dreamweaver是一款非常不错的软件设计工具了,如果你碰到在使用 Dreamweaver时 查找和替换窗口不见了我们可以来看看下面的办法。 最近用Dreamweaver8遇到了一种很...2016-10-02
- */ $str="hello world"; //定义字符串 $result=str_word_count($str); //查找单词个数 echo $result; //输出的结果 echo "<br>"; $re...2016-11-25
- 这篇文章主要介绍了基于java查找最长字符串代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-09-15