python之折半搜索

对于已知有序数列进行某个值进行搜索，折半搜索的时间复杂度为 O(logn)，效率非常高

#二分搜索算法 递归
def search(my_list,a,left,right):
    if left == right:
        if my_list[left]!= a:
            return -1
        return  left
    middle = (left+right)//2

    if my_list[middle]< a:
        return search(my_list,a,middle+1,right)
    else:
        return search(my_list,a,left,middle)

list = [0,1,2,3,5,6,7,8,9]
a = search(list,11,0,len(list)-1)
print(a)


#二分搜索算法 迭代
def search(my_list,a):
    left= 0
    right=len(my_list)-1
    while left!=right:
        middle = (left + right) // 2
        if my_list[middle]<a:
            left = middle+1
        else:
            right = middle
    if my_list[left] != a:
        return -1
    return  left


list = [0,1,2,3,5,6,7,8,9] 
a = search(list,11,0,len(list)-1) 
print(a)

折半搜索