iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 15
0

講了幾天的資料結構,先來講幾個有關搜尋的演算法,之後再繼續接回資料結構的其他部分。

循序搜尋 (Sequential Search),說白了就是在已排序的資料中一個一個比對,直到找到為止。
最簡單的程式碼就是:

data = [1, 2, 3, 4, 5, 6, 7, 8]

def sequential_search(data, key):
    for i in data:
        if i == key : 
            print("find the key") 
            break 
            
sequential_search(data, 3)

排序的部分之前有討論過,可以再回去看看。
但我們這邊稍微來個變化。

我們設一個新的陣列,可以將要搜尋的值放置在新陣列的前端或末端(這邊設在前端)。然後藉由排列原本陣列並將資料放入到新陣列中,從新陣列的末端開始一一往回找,找到後並輸出。

data = [1, 2, 3, 4, 5, 6, 7, 8]

def sequential_search(data, key):
    tmp = [0] * (len(data) + 1)    #設一個空陣列,長度為data長度+1
    for i in range(1, len(data)):  #將data的值給到tmp
        tmp[i] = data[i - 1]
    tmp[0] = key                   #設定key值
    i = len(data)                  #設定索引並開始比較
    while tmp[i] != tmp[0]:
        i -= 1
    return i - 1                   #回傳索引

index = sequential_search(data, 2)
if index >= 0:
    print("finde the index: " + str(index))
else:
    print("can't find the index")

上一篇
[資料結構] 堆積 (Heap)
下一篇
[演算法] 二分搜尋 (Binary Search)
系列文
30天學演算法和資料結構31

尚未有邦友留言

立即登入留言