資料結構學習-python實作-資料查找--0410

2023-04-13 23:26:42

資料查找算法的實質是資料的比對。

1.确定基本步驟
2.步驟足夠簡單，并反複執行。
3.查找次數介于1和n之間，平均為n/2，算法複雜度為O(n)

# 無序表的順序查找
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))

複制