时间:2021-05-22
前提:升序数组,待查元素在数组中。
二分查找:就是一个递归函数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)}")结果如下:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
二分查找BinarySearch的思想:以有序表表示静态查找表时,查找函数可以用二分查找来实现。二分查找(BinarySearch)的查找过程是:先确定待查记录
本文实例讲述了Java实现二分查找算法。分享给大家供大家参考。具体如下:1.前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序2.原理
C++中二分查找递归非递归实现并分析二分查找在有序数列的查找过程中算法复杂度低,并且效率很高。因此较为受我们追捧。其实二分查找算法,是一个很经典的算法。但是呢,
C语言数据结构中二分查找递归非递归实现并分析前言:二分查找在有序数列的查找过程中算法复杂度低,并且效率很高。因此较为受我们追捧。其实二分查找算法,是一个很经典的
本文实例为大家分享了Java实现二分查找的变种,供大家参考,具体内容如下普通二分查找:先回顾一下普通的二分查找注意:二分查找有这样一个问题:当数组中数有重复时,