简介二分查找算法与相关的Python实现示例
程序员文章站
2022-04-10 12:24:24
...
二分查找Binary Search的思想:
以有序表表示静态查找表时,查找函数可以用二分查找来实现。
二分查找(Binary Search)的查找过程是:先确定待查记录所在的区间,然后逐步缩小区间直到找到或找不到该记录为止。
1二分查找的时间复杂度是O(log(n)),最坏情况下的时间复杂度是O(n)。
假设 low 指向区间下界,high 指向区间上界,mid 指向区间的中间位置,则 mid = (low + high) / 2;
具体过程:
1.先将关键字与 mid 指向的元素比较,如果相等则返回mid。
2.关键字小于 mid 指向的元素关键字,则在 [ low, mid-1 ]区间中继续进行二分查找。
3.关键字大于mid 指向的元素关键字,则在[ mid +1 , high] 区间中继续进行二分查找。
以有序表表示静态查找表时,查找函数可以用二分查找来实现。
二分查找(Binary Search)的查找过程是:先确定待查记录所在的区间,然后逐步缩小区间直到找到或找不到该记录为止。
1二分查找的时间复杂度是O(log(n)),最坏情况下的时间复杂度是O(n)。
假设 low 指向区间下界,high 指向区间上界,mid 指向区间的中间位置,则 mid = (low + high) / 2;
具体过程:
1.先将关键字与 mid 指向的元素比较,如果相等则返回mid。
2.关键字小于 mid 指向的元素关键字,则在 [ low, mid-1 ]区间中继续进行二分查找。
3.关键字大于mid 指向的元素关键字,则在[ mid +1 , high] 区间中继续进行二分查找。
用Python实现二分查找示例:
>>> def find(self, num): l = len(self) first = 0 end = l - 1 mid = 0 if l == 0: self.insert(0,num) return False while first self[mid]: first = mid + 1 elif num num: self.insert(first, num) return False elif self[first] end: self.insert(first, num) return False else: return True >>> list_d = ['a','b','c','d','e','f','d','t'] >>> value_d = 't' >>> aa=find(list_d,value_d) >>> aa True >>> value_d='ha' >>> aa=find(list_d,value_d) >>> aa False
声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。
相关文章
相关视频
上一篇: php数据对象映射模式实例详解
推荐阅读
-
Python实现查找数组中任意第k大的数字算法示例
-
Python实现在某个数组中查找一个值的算法示例
-
Python栈算法的实现与简单应用示例
-
Python基于递归算法实现的汉诺塔与Fibonacci数列示例
-
Python cookbook(数据结构与算法)实现对不原生支持比较操作的对象排序算法示例
-
python二分查找算法的递归实现方法
-
Python cookbook(数据结构与算法)找到最大或最小的N个元素实现方法示例
-
Python cookbook(数据结构与算法)实现优先级队列的方法示例
-
PHP基于二分法实现数组查找功能示例【循环与递归算法】
-
Python cookbook(数据结构与算法)实现查找两个字典相同点的方法