数据结构学习-python实现-数据查找--0410

# 无序表的顺序查找
def sequentialsearch(alist, item):
    pos = 0
    found = False

    while pos < len(alist) and not found:  # 退出while循环的两种方式
        if alist[pos] == item:
            found = True
        else:
            pos += 1

    return found


testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialsearch(testlist, 3))
print(sequentialsearch(testlist, 13))

# 有序表的顺序查找，可以相对的减少查询次数，并不能改变复杂度的数量级。
def ordersequentialsearch(alist, item):
    pos = 0
    found = False
    stop = False
    while pos < len(alist) and not found and not stop:
        if alist[pos] == item:
            found = True
        else:
            if alist[pos] > item:
                stop = True
            else:
                pos += 1
    return found


testlist01 = [0, 1, 2, 3, 8, 15, 19, 32, 44]
print(ordersequentialsearch(testlist01, 15))
print(ordersequentialsearch(testlist01, 9))

# 以下代码为二分查找，基于有序表的查找方法。其算法复杂度为O(log(n))可进行相应的演化，比如：
# 插值查找：根据查找值在数据列中的相对位置，距离最大值与最小值的相对比例位置，进行划分。
# 斐波那契查找： 基于黄金分割比例的查找。试图改变概率。
def binarysearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False

    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found


testlist = [0, 1, 2, 8, 13, 17, 19, 33, 45]
print(binarysearch(testlist, 45))
print(binarysearch(testlist, 14))