四种版本的二分查找算法

[xxleyi]

def bin_find_v1(v, lo, hi, e):
    if lo >= hi:
        return -1
    else:
        mi = (lo + hi) // 2
        if v[mi] == e:
            return mi
        if v[mi] > e:
            return bin_find_v1(v, lo, mi, e)
        else:
            return bin_find_v1(v, mi+1, hi, e)

v = [1, 2, 3, 4, 5, 6, 7]
bin_find_v1(v, 0, len(v), 3)

版本一：三个区间的二分查找，且头尾区间不均衡。
Python tutor 演示链接

[xxleyi]

def bin_find_v3(v, lo, hi, e):
    if lo < hi - 1:
        mi = (lo + hi) // 2
        if e < v[mi]:
            hi = mi
        else:
            lo = mi
        return bin_find_v3(v, lo, hi, e)
    return (lo if v[lo] == e else -1)

v = [1, 2, 3, 4, 5, 6, 7]
bin_find_v3(v, 0, len(v), 4)

版本三：两个区间的二分查找，查找不到时返回 -1
Python tutor 演示链接

[xxleyi]

def bin_find_v4(v, lo, hi, e):
    if lo < hi:
        mi = (lo + hi) // 2
        if e < v[mi]:
            hi = mi
        else:
            lo = mi + 1
        return bin_find_v4(v, lo, hi, e)
    return lo - 1
     
v = [1, 2, 3, 4, 5, 6, 7]

bin_find_v4(v, 0, len(v), 4)

版本四：两个区间的二分查找，返回不大于e的最后一个元素的 rank
Python tutor 演示链接

[xxleyi]

def bin_find_v1(v, lo, hi, e):
    if lo >= hi:
        return -1
    else:
        mi = (lo + hi) // 2
        if v[mi] == e:
            return mi
        if v[mi] > e:
            return bin_find_v1(v, lo, mi, e)
        else:
            return bin_find_v1(v, mi+1, hi, e)

v = [1, 2, 3, 4, 5, 6, 7]
bin_find_v1(v, 0, len(v), 3)

版本一：三个区间的二分查找，且头尾区间不均衡。
Python tutor 演示链接

---

版本 2: 黄金分割二分查找

def bin_find_v2(v, lo, hi, e):
    fib = Fib(hi - lo)
    while lo < hi:
        while hi - lo < fib.get():
            fib.prev()
        mi = lo + fib.get() - 1
        if e < v[mi]:
            hi = mi
        elif e > v[mi]:
            lo = mi
        else:
            return mi
            
    return -1
   
 
class Fib(object):
    
    def __init__(self, n):
        
        self._f = 1
        self._g = 0
        while self._g < n:
            self.next()
            
    def next(self):
        self._g, self._f = self._g + self._f, self._g
        return self._g
        
    def prev(self):
        self._g, self._f = self._f, self._g - self._f
        return self._g
        
    def get(self):
        return self._g
        

v = [1, 2, 3, 4, 5, 6, 7]
print(bin_find_v2(v, 0, len(v), 5))

Python Tutor fib sort 演示