Python基础查找算法

def sequential_search(lst, key):
    length = len(lst)
    for i in range(length):
        if lst[i] == key:
            return i
    else:
        return "不存在"
def main():
    alist = [5,3,7,2,12,45,16,23]       #测试列表
    print("所要查找的元素的位置是：",sequential_search(alist, 12)) #查找数据12
    print("所要查找的元素的位置是：",sequential_search(alist, 36)) #查找数据36
main()  #调用main函数

def max_min(lst):
    max = min = lst[0]
    for i in range(len(lst)):
        if lst[i] > max:
            max = lst[i]
        if lst[i]< min:
            min = lst[i]
    return (max,min)
def main():
    alist = [5,3,7,2,12,45,16,23]       #测试列表
    print("列表中元素的(最大值,最小值)=",max_min(alist)) #查找列表的最大值最小值
main()

def binary_search(lst, key):
    low = 0                    #左边界
    high = len(lst) - 1        #右边界
    time = 0                   #记录查找次数
    while low <= high:           #左边界小于等于右边界，则循环
        time += 1
        mid = (low + high)//2
        if  lst[mid]>key:        #中间位置元素大于要查找的值
            high = mid - 1
        elif lst[mid]<key:
            low = mid + 1
        else:
            print("折半查找的次数: %d" % time)
            print("所要查找的值在列表中的索引号是：", end='')
            return mid
    print("折半查找的次数: %d" % time)
    return '未找到'         #查找不成功，'未找到'
def main():
    alist = [5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92]
    result = binary_search(alist, 13)
    print(result)
main()

def binary_search(lst, low, high, key):
    mid = int((low + high)/2)
    if high < low:
        return False
    elif lst[mid]==key:
        print("所要查找的值在列表中的索引号是：", end='')
        return mid
    elif lst[mid]> key:
        high = mid - 1
        return binary_search(lst, low, high, key)
    else:
        low = mid + 1
        return binary_search(lst, low, high, key)
if __name__=="__main__" :
    alist = [5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92]
    low = 0
    high = len(alist) - 1
    result = binary_search(alist, 0, high, 21)
    print(result)

def interpolation_search(lst, low, high, key):
    time = 0   #用来记录查找次数
    while low < high:
        time += 1
        # 计算mid值是插值算法的核心代码
        mid = low + int((high - low) * (key - lst[low])/(lst[high] - lst[low]))
        print("mid={0}, low={1}, high={2}".format(mid, low, high))
        if lst[mid] > key:
            high = mid - 1
        elif lst[mid] < key:
            low = mid + 1
        else:
            print("插值查找%s的次数:%s"%(key, time))  #打印插值查找的次数
            return mid
    print("插值查找%s的次数:%s"%(key, time))
    return False
def main():
    alist = [5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92]
    low = 0
    high = len(alist) - 1
    interpolation_search(alist, low, high, 13)
main()