算法筆記(六)
檢索算法
- 算法筆記(六)
- 前言
- 一、線性查找
-
- 1.什麼是線性查找
- 2.需求規則
- 3.人工圖示示範
- 4.代碼實作
- 二、二分查找
-
- 1.什麼是二分查找
- 2.需求規則
- 3.人工圖示示範
- 4.代碼實作
- 三.插值查找
-
- 1.什麼是插值查找
- 2.需求規則
- 3.人工圖示示範
- 4.代碼實作
- 四.斐波那契查找
-
- 1.什麼是斐波那契查找
- 2.需求規則
- 3.人工圖示示範
- 4.代碼實作
- 五.分塊查找
-
- 1.什麼是分塊查找
- 2.需求規則
- 3.人工圖示
- 4.代碼實作
- 六.哈希查找
-
- 1.什麼是哈希查找
- 1.需求規則
- 2.人工圖示示範
- 4.代碼實作
- 七.回溯查找
-
- 1.什麼是回溯查找
- 2.需求規則
- 3.人工圖示示範
- 4.代碼實作
- 總結
前言
檢索算法又叫查找算法，可以分為排序檢索和非排序檢索兩大類。排序的資料為高校檢索提供了基礎。當然非排序也存在，隻不過效率很低。本章一起來學習幾種檢索算法。
一、線性查找
1.什麼是線性查找
線性查找(Linear Search)又叫作順序查找，是最簡單的一種查找方法。
2.需求規則
- 實作思路：從第一個元素開始依次查找比較，若查找成功，則傳回找到元素的下标或确認資訊；若查找失敗，則傳回查找失敗資訊。
- 線性查找既可以從左邊開始，也可以從右邊開始。
- 線性查找可以用于排序數列的查找，也可以用于無序數列的查找。
3.人工圖示示範
圖所示為線性查找過程，從左到右依次比較查找。查找值key=5時，
傳回沒有找到;
4.代碼實作
def linearfind(arr, key):
n = len(arr)
i = 0
while i < n:
if arr[i] == key:
return i
i += 1
return -1
s1 = [66, 79, 65, 25, 54, 99, 101, 100]
key = 6
r = linearfind(s1, key)
if r != -1:
print(f'{key}被找到，在第{r}位上')
else:
print(f"{key}沒有被找到")
運作結果
二、二分查找
1.什麼是二分查找
二分查找( Binary Search)算法采用折半查找思路，實作對有序元素的快速查找。
2.需求規則
- 前提條件是資料已經排序。
- 在數列中取中間下标值為mid的元素E,然後将元素E與查找值key進行比較，如果相等即查找成功，并傳回其下标mid;如果E>key,則在左邊範圍内繼續取新的mid下标值元素，判斷兩者大小:如果E<key,則在右邊範圍内繼續取新的mid下标值元素，判斷兩者大小。上述過程疊代進行，直到查找範圍縮小為一個元素，查找結束并傳回查找結果。
3.人工圖示示範
圖示為二分查找過程，清單共有n=11個元素。
第一次，取中間值mi-1/2-5,其左邊範圍為left=0、 右邊範圍為right=10， 比較結果
key-55在右半邊的範圍内。
第二次，取新的中間值mid-s/2 2,其左邊範圍為lef-5+1、右邊範圍為igh=10,比較結果
key-55在右半邊的範圍内。
第三次，取新的中間值m-2/2=I,其左邊範圍為let-6+2+1.右邊範圍為rgh=l0,比較結
果在下标10處找到55。
4.代碼實作
def binaryrearch(arr, key):
left = 0
right = len(arr)
while left <= right:
mid = (right - left) // 2 # 二分法中間位置
if arr[left + mid] < key: # key 在右半範圍
left = left + mid + 1
elif arr[left + mid] > key: # 左半範圍
left = left + mid - 1
else:
return left + mid # 找到下标
return -1
s1 = [0, 10, 20, 30, 40, 50, 60, 70, 80]
print(f"查找清單{s1}")
key = 40
r = binaryrearch(s1, key)
if r == -1:
print(f"未找到{key}元素")
else:
print(f"在清單第{r}找到{key}元素")
運作結果
三.插值查找
1.什麼是插值查找
插值查找(Interpolation Search) 是基于有序數列的元素查找，在采納二分查找算法的思路基礎上進行了改進。在最小值、最大值範圍内，用公式确定中間分割比較點mid
2.需求規則
- 圖式的基本思路是用最大值與最小值之差和中間值與最小值之差的比值乘以最大值和最小值下标範圍差，以确定查找中間範圍下标值mid.注意最大值和最小值下标範圍就是要查找的範圍，而後确定範圍的中間值，以分割思路進行比較。
- 通過比較arr[mid]與key的大小，确定結果是相等、小于還是大于，然後決定是否再縮小分割，直到找到元素值或查找結束。
3.人工圖示示範
圖所示為插值查找過程，left=0, right=8， mid=8*(50-0)/50=8。
4.代碼實作
def valuyesearch(arr, key):
left = 0
right = len(arr) - 1
while left < right:
mid = left + int((right - left) * (key - arr[left]) / (arr[right] - arr[left]))
if key < arr[mid]:
right = mid - 1
elif key > arr[mid]:
left = mid + 1
else:
return mid
return -1
s1 = [0, 10, 20, 30, 40, 50, 60, 70, 80]
print(f"查找清單{s1}")
key = 60
r = valuyesearch(s1, key)
if r == -1:
print(f"未找到{key}元素")
else:
print(f"在清單第{r}找到{key}元素")
運作結果
四.斐波那契查找
1.什麼是斐波那契查找
斐波那契數列(Fibonacci Sequence)又稱黃金分割數列，指的是這樣一個數列: 1、 1、 2、3、5、8、13、21、······ 在數學上斐波那契被遞歸方法如下定義: F(1)=1， F(2)=1, F(n)=F(n 1)+F(n-2) (n≥2)。該數列越往後，相鄰的兩個數的比值越趨向于黃金比例值(0.618)。
斐波那契查找就是在二分查找的基礎上根據斐波那契數列對資料進行分割的。
2.需求規則
- 提供有序排列的清單對象s=[0,3,5,7,10,30,50,70,80,100]， 其個數n=10。
- 利用斐波那契數列1、1、2、3、5、8、13、21、.，作為下标來分割清單元素範圍。
- 為了滿足斐波那契數列中下标範圍要求，提供的清單如果不滿足要求，則預設的數字用清單最後一個元素重複填補，如這裡的n=10,但是10後最靠近的斐波那契數是13， 其缺失的下标為10、11 和12的元素都用100來填補。
- 比較查找的key值在斐波那契數列的哪個範圍内，找到傳回，找不到給予提示。
3.人工圖示示範
圖示為斐波那契查找過程。
第一步，判斷s數列的長度是否滿足n=13，如果不滿足，則用最後一個元素100 補充3個 100 (13-n=3)。
第二步，中間下标值mid取最右邊值13-1 (斐波那契最後一個數是13)， 因為70<100，說明70值範圍在左邊。
第三步，中間下标值mid取8-1 (斐波那契倒數第2個數是8)，key=70, 找到元素。
4.代碼實作
def fibonaccisearch(arr,key):
n = len(arr)
i = 1
F = [1,1,]
while F[i] <= n:
F.append(F[i-1]+F[i])
i += 1
print(f'生成最右邊的斐波那契數為{F}')
left = 0
right = n - 1
f = F[i]
print(f'生成的最右邊的斐波那契數為{f}')
i = 0
while i< f - n:
arr.append(arr[right])
i += 1
print(arr)
k = len(F)
t = 0
while left <= right:
t += 1
if k < 2:
mid = left
else:
mid = left + F[k-1] - 1
print(f"left={left},mid={mid},right={right}")
if key < arr[mid]:
right = mid - 1
k -= 1
elif key > arr[mid]:
left = mid + 1
k -= 2
else:
print(f"查找次數{t}")
if mid <= right:
return mid
else:
return right
print(f"查找次數{t}")
return False
key = 70
s1 = [0,3,5,7,10,30,50,80,100]
r = fibonaccisearch(s1,key)
if r == False:
print(f"{key}沒有在清單中找到")
else:
print(f"查找{key}在清單裡的下标{r}")
運作結果
五.分塊查找
1.什麼是分塊查找
分塊查找，又叫索引順序查找，是順序查找的一種改進方法。
2.需求規則
- 輸入清單元素分塊之間的值順序排序
- 實作思路是把數列元素分為m個分塊，m<=n，其中n為清單長度。建立每個分塊最大值的索引表，通過查找值key與索引表值範圍的比較，确定其查找範圍或傳回沒有該值；然後，進一步根據查找範圍确定查找值所在分塊，用線性查找方法查找所在分塊裡的查找内容，得出查找結果。
3.人工圖示
- 圖示為分塊查找過程。查找的前提條件是分塊之間值是順序的，例如，1分塊内的元素都小于2分塊的，2裡面的元素均小于3方塊裡的，但允許每個方塊裡的元素無序。
- 第一步，先在索引表裡按順序存儲每個分塊的最大值，這意味着第一個元素8的下表0剛好對應分塊1，第二個元素89的下标1對應分塊2，第三個元素200的下标2對應分塊3.
- 第二部，通過關鍵值key=2與索引表值比較，得出元素2在範圍8内，通過元素8的下标0，确定元素2屬于1分塊範圍
- 第三步，在1分塊子清單裡用線性查找法找元素2，找到2并傳回其清單下标值2，查找結束。
4.代碼實作
def linearfind(arr, key):
n = len(arr)
i = 0
while i < n:
if arr[i] == key:
return i
i += 1
return -1
def blocksearch(arr, key, index, n):
b_max = -1
j = 0
for i in index:
j += 1
if key <= i:
b_max = i
break
if b_max == -1:
return -1
print(f"塊内最大值為{b_max}")
r = linearfind(arr[(j - 1) * n:(j * n - 1)], key)
print(f"線性查找結果：{r}")
if r == -1:
return -1
else:
return (j - 1) * n + r
s1 = [1, 4, 2, 8, 3, 10, 89, 20, 19, 50, 200, 128, 121, 120, 110]
index = [8, 89, 200]
key = 2
r = blocksearch(s1, key, index, 5)
if r == -1:
print(f"{key}在清單裡不存在")
else:
print(f"{key}在清單裡的下标為{r}")
運作結果
六.哈希查找
1.什麼是哈希查找
哈希查找算法采用鍵值對存儲資料的哈希表，通過哈希函數決定存儲位址，并利用元素對應的位址直接在哈希表裡進行1次通路即解決查找問題，時間複雜程度為O(1)，效率很高。
1.需求規則
- 擷取哈希表的長度n
- 利用元素值%n取餘，獲得對應的位址(字典的鍵)；在位址發生沖突時，通過增1方式試探産生下一個位址
- 建立字典存儲鍵值（位址-元素）
- 再利用元素值%n求餘，在字典裡通過位址，一次通路找到值或給出找不到值的提示
2.人工圖示示範
第一步，建立哈希表，哈希表的元素為鍵值對，在python語言裡可以看作字典。鍵用于存放唯一性位址，值用于存放資料。
第二步，用哈希函數(hash()産生鍵（address）)，産生鍵的唯一要求是産生具有唯一位址的數值。産生鍵的算法有很多種，這裡采用了除留餘數法，公式為元素值%n，n為哈希表的長度；對于重複發生沖突的位址，采用試探下一個位址的方法解決（觀察48産生的位址9）
第三步，查找元素時，也采用哈希函數算法先找到位址，然後在哈希表裡1次找到對應的值（如果找不到，試探下一個位址，直到哈希表結束）。
4.代碼實作
maxsize = 20
hashtable = {i: None for i in range(maxsize)}
print(f"哈希表大小為{len(hashtable)}")
def hash(value):
address = value % maxsize
if hashtable[address] == None:
return address
else:
while address < maxsize:
address += 1
if hashtable[address] == None:
return address
return -1
def buildhashtable(values):
for value in values:
address = hash(value)
print(f"建立的鍵值對({address},{value})")
if address != -1:
hashtable[address] = value
else:
print(f"數值{value}存放的哈希表位址不夠")
return hashtable
def findvalue(hasht, value):
address = value % maxsize
if hasht[address] == value:
return True
else:
address += 1
while address < maxsize:
if hasht[address] == value:
return True
address += 1
return False
s1 = [20, 30, 1, 2, 5, 8, 23, 44, 48]
value = 44
if findvalue(buildhashtable(s1), value):
print(f"在哈希表裡找到{value}")
else:
print(f"在哈希表裡找不到{value}")
運作結果
七.回溯查找
1.什麼是回溯查找
回溯算法(Backtracking Algorithm)是一個類 似枚舉的搜尋嘗試過程，在嘗試過程中尋找問題的解，當發現條件不滿足要求時，回退尋找另外路徑求解，反複疊代上述過程，直到找出滿足要求的所有條件(即為一個解)，或者不存在解。
許多複雜的、規模較大的問題都可以使用回溯查找法求解，該算法有“通用解題方法”的美稱。
2.需求規則
- 建立回溯空間的資料結構(二維表或二維數組)。
- 按照一定條件試探性地在空間搜尋，成功繼續往下搜尋;不成功回退，選擇另外一個方 向繼續試探。
- 直到所有的條件都滿足，求得最優解;或得出不存在最優解。
3.人工圖示示範
圖示為走迷宮主要思路。左上角第一個矩陣中0代表牆，1代表道路。要求隻能從第1列的任意一個口進入，最後一列任意一個口出去， 才算走出迷宮。圖右上角是一.條能走通的迷宮路。
- 規則1.理論上除了邊角節點外，目前節點往下一步走，需要考慮的節點最多有四個(右、下、左、上)，圖左下角顯示箭頭所指中間圈裡的1代表可走節點，四周從右、下、左、上四個緊鄰節點的值判斷是從該節點出發，然後需要判斷哪條路可以走。 顯然，這個節點右邊有一個1，可以往右走。
- 規則二。當碰到斷頭路時，不能再走下去了，隻能往回走，尋找下一個出路，這叫回溯過程。如圖右下角圈裡的1，上，右，下都是牆壁，無法繼續往前走，于是通過record記錄的前一步的1往回退，并在maze裡把目前1設定為0，代表不能走。繼續利用規則1尋找下一個可走的道路，直到走到最右列，隻找到一條可通的路。
4.代碼實作
def findnext(m, record, r, c):
n = len(m)
if (c + 1 < n):
if record[r][c + 1] == 0:
if m[r][c + 1] == 1:
record[r][c + 1] = 1
return r, c + 1
else:
b_r, b_c = r, c + 1
if r + 1 < n:
if record[r + 1][c] == 0:
if m[r + 1][c] == 1:
record[r + 1][c] = 1
return r + 1, c
else:
b_r, b_c = r + 1, c
if r - 1 >= 0:
if record[r - 1][c] == 0:
if m[r - 1][c] == 1:
record[r - 1][c] = 1
return r - 1, c
else:
b_r, b_c = r - 1, c
if c - 1 >= 0:
if record[r][c - 1] == 0:
if m[r][c - 1] == 1:
record[r][c - 1] = 1
return r, c - 1
else:
b_r, b_c = r, c - 1
m[r][c] = 0
if r + 1 == n and m[r][0] == 0:
print(r, c)
b_r, b_c = r + 1, 0
return b_r, b_c
def solution_maze(m, record):
row, col = 0, 0
n = len(m)
i = 0
while i < n:
if m[i][0] == 1:
row = i
record[i][0] = 1
break
i += 1
if i == n - 1:
print("第一列無入門地方，終止執行")
while i < n:
if (row < n and row >= 0) and (col < n and col >= 0):
if col == n - 1:
for one in record:
print(one)
return 1
row, col = findnext(m, record, row, col)
if col == 0:
i += 1
row = i
return 0
if __name__ == '__main__':
maze = [[0, 1, 0, 1, 1, 1, 1, 1, 0],
[1, 1, 0, 1, 0, 1, 0, 1, 1],
[0, 1, 1, 1, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 1, 1, 0, 0, 0],
[0, 1, 1, 1, 1, 0, 1, 1, 1],
[0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 0, 1],
[0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 1]]
n = len(maze)
recordpath = [([0]*n) for _ in range(n)]
solution_maze(maze,recordpath)
運作結果
總結
有關檢索算法就這些了，有哪塊不懂得歡迎 點選這裡加入直接問問題，一起探讨。