四种版本的二分查找算法 about learning_list HOT 3 OPEN

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)

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)

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))