二分查找法怎么在python项目中实现?很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。
1、二分查找
在一个有序并且无重复的列表中,对该列表的元素进行查找。
2、特点
(1)必须针对于有序列表
(2)该列表必须无重复
(3)按下标索引查找
3、使用方法
非递归实现:
def binary_search(alist, item): """二分查找 非递归方式""" n = len(alist) start = 0 end = n - 1 while start <= end: mid = (start + end) // 2 if alist[mid] == item: return True elif item < alist[mid]: end = mid - 1 else: start = mid + 1 return False if __name__ == '__main__': li = [17, 20, 26, 31, 44, 54, 55, 77, 93] # print(binary_search(li, 55)) # print(binary_search(li, 100))
递归实现:
def binary_search_2(alist, item): """二分查找 递归方式""" n = len(alist) if 0 == n: return False mid = n // 2 if alist[mid] == item: return True elif item < alist[mid]: return binary_search_2(alist[:mid], item) else: return binary_search_2(alist[mid + 1:], item) if __name__ == '__main__': li = [17, 20, 26, 31, 44, 54, 55, 77, 93] # print(binary_search(li, 55)) # print(binary_search(li, 100))
基础知识点扩展:
介绍
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
前提
必须待查找的序列有序
时间复杂度
O(log2n)
原理
1)确定该期间的中间位置K
2)将查找的值t与array[k]比较,若相等,查找成功返回此位置;否则确定新的查找区域,继续二分查找。
3)区域确定过程:
若array[k]>t,由于数组有序,所以array[k,k+1,……,high]>t;故新的区间为array[low, ..., K-1];
反之,若array[k]<t对应查找区间为array[k+1, ..., high]
看完上述内容是否对您有帮助呢?如果还想对相关知识有进一步的了解或阅读更多相关文章,请关注亿速云行业资讯频道,感谢您对亿速云的支持。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。