GCSE 計算機科學/搜尋演算法
如果您有一個未排序的列表（或陣列），那麼最簡單的搜尋演算法是線性搜尋。它逐個遍歷列表項，並與要搜尋的項進行比較。如果比較成功，則演算法已找到該項。如果所有比較都失敗，則該項不存在於陣列或列表中。在最簡單的變體中，演算法返回一個布林值以指示成功或失敗。
|
練習：線性搜尋 考慮字串列表“Cat”、“Mouse”、“Frog”、“Lion”、“Panda”、“Llama”、“Bee”，按此順序。找到“Panda”需要多少次比較？ 答案 5 當搜尋“Camel”時需要多少次比較？ 答案 需要 7 次比較才能得出該字串不在列表中的結論。 |
正如上一個問題所指出的，線性搜尋可能需要與列表中專案數量一樣多的比較，因此在數百萬個名字列表（例如一個國家的選民登記冊）中搜索一個名字可能需要很長時間。
如果您的列表按升序排序，或者透過排序演算法按升序排序，那麼您可以執行二分搜尋。這涉及在每次比較時將資料分成兩半，從而更快地“縮小”到專案必須存在於列表中的部分，如果它存在於列表中。這會導致更好的效能。
- 讓我們在以下排序列表中搜索名字 Miles
- Ali, Bernie, Claire, Mohammed, Peter, Simon, Yvonne
- 我們將 Miles 與中間的名字 Mohammed 進行比較
- Ali, Bernie, Claire, Mohammed, Peter, Simon, Yvonne
- Miles 按字母順序排在 Mohammed 之前，因此我們知道 Miles 不會出現在 Mohammed 的右邊。因此，我們可以“丟棄”列表的右半部分
- Ali, Bernie, Claire,
Mohammed, Peter, Simon, Yvonne
- 現在我們將 Miles 與剩餘列表中的中間名字 Bernie 進行比較
- Ali, Bernie, Claire,
Mohammed, Peter, Simon, Yvonne
- Miles 按字母順序排在 Bernie 之後，所以我們可以丟棄左邊
Ali, Bernie, Claire,Mohammed, Peter, Simon, Yvonne
- 最後，我們將 Miles 與這個單項列表的中間名字 Claire 進行比較
Ali, Bernie, Claire,Mohammed, Peter, Simon, Yvonne
- Miles 與 Claire 不一樣，沒有更多項可以比較，所以我們知道 Miles 不在列表中。
這僅使用二分搜尋進行了 3 次比較，使用線性搜尋則需要 7 次比較。當列表很大時，情況會更好。例如，一個包含 1,000,000,000 個專案的列表，使用二分搜尋最多隻需要 30 次比較！擁有排序資料非常有用。
|
練習：線性搜尋與二分搜尋 排序資料對線性搜尋也很有用。修改後的線性搜尋演算法如何在搜尋 Miles 時進行少於 7 次比較？ 答案 修改後的線性搜尋將在 4 次比較後（與 Ali、Bernie、Claire 和 Mohammed 比較）知道 Miles 不在排序列表中，因為 Miles 應該出現在 Mohammed 之前。 對於上面顯示的 7 個名字的列表，你能想到線性搜尋比二分搜尋更快的案例嗎？ 答案 如果我們搜尋列表中的第一個專案 Ali，二分搜尋仍然需要 3 次比較（與 Mohammed、Bernie 和 Ali 比較），但線性搜尋只需要 1 次比較。 對於大型列表的線性搜尋，最佳情況是所搜尋的專案在第一個位置。大型列表的二分搜尋的最佳情況是什麼？ 答案 如果所搜尋的專案位於列表的中間，則二分搜尋只需要 1 次比較。 |
二分搜尋在排序陣列中定位專案的所在位置。每次比較失敗後，二分搜尋都會將搜尋空間減少一半。它的效率如何？對於 x 個專案的搜尋次數是多少？公式是什麼？為什麼它比線性搜尋更好。
如何計算 x 大小陣列上的最大搜索次數 (n)
2^n > size of list (x) where n = max searches
例如，如果我們有一個 3 個專案的陣列
2^2 = 4 > 3 therefore max searches = 2
|
練習：二分搜尋 給定一個包含 256 個專案的排序列表，找到一個專案所需的最大搜索次數是多少？
答案 9 as: 給定一個包含 1000 個專案的排序列表，找到一個專案所需的最大搜索次數是多少？
答案 10 as: 2^n > size of list where n = max searches 2^10 = 1024 > 1000 |