二分(折半)查找

#1.非递归实现(待查找的元素必须在一个有序的序列中)
def binary_search(alist,value):
    first=0
    last=len(alist)-1
    while first<=last:
        mid=(first+last)//2
        if alist[mid]==value:
            return True
        elif alist[mid]>value:
            last=mid-1
        else:
            first=mid+1
    return False
list=[1,2,3,7,12,45,67,89]
print(binary_search(list,2))
print(binary_search(list,5))

#2.递归实现
#时间复杂度：最优时间复杂度：O(1),最坏时间复杂度：O(logn)
def binary_search(alist,value):
    if len(alist)==0:
        return False
    else:
        mid=len(alist)//2
        if alist[mid]==value:#找到了要查找到的值
            return True
        elif alist[mid]>value:#中间的值大于要查找的值，则在左边区间进行查找
            return binary_search(alist[:mid],value)
        else: #中间的值小于要查找的值，则在右边的区间进行查找
            return binary_search(alist[mid+1:],value)

list=[1,2,3,7,12,45,67,89]
print(binary_search(list,2))
print(binary_search(list,5))