简介二分查找算法与相关的Python实现示例
发布时间:2020-12-16 21:28:05 所属栏目:Python 来源:网络整理
导读:二分查找Binary Search的思想: 以有序表表示静态查找表时,查找函数可以用二分查找来实现。 二分查找(Binary Search)的查找过程是:先确定待查记录所在的区间,然后逐步缩小区间直到找到或找不到该记录为止。 1二分查找的时间复杂度是O(log(n)),最坏情况
二分查找Binary Search的思想: 用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 < end: mid = (first + end)/2 if num > self[mid]: first = mid + 1 elif num < self[mid]: end = mid - 1 else: break if first == end: if self[first] > num: self.insert(first,num) return False elif self[first] < num: self.insert(first + 1,num) return False else: return True elif first > end: self.insert(first,num) return False else: return True >>> list_d = ['a','b','c','d','e','f','t'] >>> value_d = 't' >>> aa=find(list_d,value_d) >>> aa True >>> value_d='ha' >>> aa=find(list_d,value_d) >>> aa False (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |