首页 > 代码库 > 折半查找
折半查找
折半查找(二分查找)是个常用基础算法了。个人觉得主要注意事项就是不要写递归吧。其实实际应用中递归能不用就不用,压栈出栈效率较低而且递归层级太多容易爆栈。
只要分别维护一个指向当前首尾的值即可消除递归。
实现: 传入一个数组arr(已升序排序)和要找的值k。找到了返回下标,找不到返回-1.
def bsearch(arr, k): begin = 0 end = len(arr) - 1 while begin < end - 1: peak = (begin + end) // 2 if arr[peak] == k: return peak elif arr[peak] > k: end = peak else: begin = peak if arr[begin] != k and arr[end] != k: return -1 elif arr[begin] == k: return begin else: return end
折半查找
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。