python查找算法

查找算法

顺序查找

def linear_search(li, val):
    for i, idx in enumerate(li):
        if i == val:
            return idx
    return None

时间复杂度：O（n）

二分查找

def binary_search1(lis, val):
    left = 0
    right = len(li) - 1
    while left < right:
        mid = (left + right) // 2

        if val == li[mid]:
            return mid
        elif val > li[mid]:
            left = mid + 1
        elif val < li[mid]:
            right = mid - 1
    else:
        return None
# 递归查找
def binary_search2(lis, val):
    l = 0
    r = len(lis) - 1
    mid = (l + r) // 2
    print(val, mid, lis[mid], lis[-1], lis[0])
    if val == lis[mid]:
        return True
    elif val > lis[mid]:
        return binary_search2(lis[mid + 1:], val)
    else:
        return binary_search2(lis[:mid], val)