首页 > 代码库 > 折半查找

折半查找

  折半查找(二分查找)是个常用基础算法了。个人觉得主要注意事项就是不要写递归吧。其实实际应用中递归能不用就不用,压栈出栈效率较低而且递归层级太多容易爆栈。

  只要分别维护一个指向当前首尾的值即可消除递归。

  实现: 传入一个数组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

 

折半查找