二分法是很常见的一种查找算法，原理很简单，但是要动手实现，还是有很多细节问题要考虑到，下面记录一下实现的过程

1.普通实现

def bisection(arr,num):
    top = len(arr)-1 # 查找范围的上边界
    bottom = 0 # 查找范围的下边界
    while top>=bottom:
        mid = (top+bottom)//2  # 取中间的值，做对比
        if arr[mid] > num:
            top = mid -1  # 范围缩小到前半段
        elif arr[mid] < num:
            bottom = mid + 1 # 范围缩小到后半段
        else:
            print('已找到')
            return mid
     else:
         print('没找到')
         return None   
a=[1,3,5,7,9,11,15,18,22,35,36,67,77,78,79,100]
bisection(a, 3)
>>
已找到
1

2.递归

def bisection2(lst,n):
    if len(lst) == 0:
        print('没找到')
        return False
    mid = len(lst)//2
    if lst[mid] == n:
        print('已找到')
        return True
    elif lst[mid]>n: # 检查前半部分
        return bisection2(lst[:mid],n) # 这里mid不需要减1，因为切片不包括又边界
    else:
        return bisection2(lst[mid+1:],n)

在第一个例子中，数组a的长度为16，如果要查询1的位置，是需要二分次数最多的，可以看到while循环了4次才能找到1，即2**4=16, log16=4 (2为底)，所以二分法的时间复杂度为O(logn)