歡迎來到搜尋演算法的世界！
各位未來的電腦科學家，大家好！本章節將探討電腦如何高效地尋找資料。試想一下，你每天搜尋了多少次東西——手機裡的聯絡人、Spotify 上的歌曲，或是使用搜尋引擎查詢事實。快速搜尋資料是電腦最基本、也最重要的工作之一！
在本節中，我們將探討電腦在搜尋資料清單時常用的兩種核心方法：線性搜尋 (Linear Search) 和 二分搜尋 (Binary Search)。理解這些演算法對於編寫快速且高效的程式至關重要。讓我們開始吧！
1. 什麼是搜尋演算法？
搜尋演算法 (Searching Algorithm) 是一種逐步執行的方法，用於從任何已儲存該項目的資料結構中檢索出某個元素（或項目）。目標很簡單：盡快找到目標項目，或者確認它不存在。
- 資料集（或清單）：這是電腦正在搜尋的項目集合（例如：名稱、價格或數字的清單）。
- 目標項目：你正在尋找的特定項目。
2. 線性搜尋 (Linear Search)
什麼是線性搜尋？
線性搜尋 (Linear Search)，有時也稱為循序搜尋 (Sequential Search)，是最簡單的方法。它的運作方式是從頭到尾，逐一檢查清單中的每一個項目。
類比：想像你有一堆 100 張未經排序的 CD，而你正在尋找一張特定的專輯。你從最上面開始，檢查第一張 CD 的標籤，然後是第二張、第三張，以此類推，直到找到它（或直到檢查完這堆 CD 的末端）。
線性搜尋的運作方式（步驟說明）
- 從清單的第一個元素開始。
- 將當前元素與目標項目進行比較。
- 如果兩者相符：找到了！搜尋立即停止。
- 如果兩者不符：移動到清單中的下一個元素。
- 重複步驟 2–4，直到找到目標或達到清單末端。
- 如果達到末端仍未找到項目，則表示該項目不在清單中。
範例：在清單中搜尋數字 55。
清單：[10, 80, 25, 55, 40]
目標：55
步驟 1：10 等於 55 嗎？不是。（移動到下一個）
步驟 2：80 等於 55 嗎？不是。（移動到下一個）
步驟 3：25 等於 55 嗎？不是。（移動到下一個）
步驟 4：55 等於 55 嗎？是！找到項目！
線性搜尋的主要特點
- 資料順序要求：它適用於未排序的清單（資料可以以任何隨機順序排列）。這是它最大的優點！
- 效率（速度）：在最壞的情況下（如果項目是最後一個，或者根本不在清單中），電腦必須檢查清單中的每一個項目。對於非常大的清單，這種方法可能會很慢。
快速複習：線性搜尋
線性搜尋既可靠又簡單，而且無論清單的順序如何都能運作。然而，對於長清單來說，它的效率可能非常低（緩慢），因為它從不跳過任何項目。
3. 二分搜尋 (Binary Search)
如果起初覺得這個方法有點複雜也不用擔心，它其實基於你可能每天都在使用的方法！二分搜尋比線性搜尋快得多，但它有一個嚴格的先決條件。
關鍵先決條件：已排序的資料
二分搜尋 (Binary Search) 演算法僅在資料集為已排序（按字母或數字順序排列）時才能運作。如果資料未經排序，則無法使用此方法！
類比：試想在字典中查詢一個定義，或在電話簿中尋找一個號碼。這些書籍是按字母順序排列的。如果它們沒有排序，你就必須使用線性搜尋（檢查每一頁！）。
二分搜尋的運作方式（「對半切」法）
二分搜尋使用「分治法」(Divide and Conquer) 的策略。它不是一次檢查一個項目，而是檢查中間的項目，並立即排除掉剩餘清單的一半。
二分搜尋的運作方式（步驟說明）
- 找到清單的中間元素。
- 將中間元素與目標項目進行比較。
-
三種可能的結果：
- 相符：如果中間項目等於目標，則搜尋結束。
- 目標較小：如果目標小於中間項目，則目標一定在清單的左半部（因為清單已排序）。你可以安心地捨棄整個右半部。
- 目標較大：如果目標大於中間項目，則目標一定在清單的右半部。你可以安心地捨棄整個左半部。
- 在剩餘的（較小的）清單中重複步驟 1–3，直到找到項目或剩餘清單變為空。
範例：在已排序的清單中搜尋數字 17。
清單：[3, 7, 10, 12, 15, 17, 20, 22, 25]
目標：17
步驟 1（第一次搜尋）：
清單有 9 個項目。中間項目是第 5 個：15。
15 等於 17 嗎？不是。
17 比 15 大還是小？大。
動作：捨棄 15 及其左側的所有內容（3, 7, 10, 12）。
步驟 2（第二次搜尋）：
剩餘清單：[17, 20, 22, 25]
新的中間項目在 20 和 22 之間。我們選擇 20。
20 等於 17 嗎？不是。
17 比 20 大還是小？小。
動作：捨棄 20 及其右側的所有內容（22, 25）。
步驟 3（第三次搜尋）：
剩餘清單：[17]
中間項目是 17。
17 等於 17 嗎？是！找到項目！
注意，即使清單有 9 個項目，我們也只用了 3 個步驟就找到了！線性搜尋可能需要 6 個步驟。對於包含 100 萬個項目的清單，二分搜尋會快得多。
記憶小撇步：二分搜尋
記住 "Binary" 的意思是「二元/兩個」。二分搜尋總是將問題分成兩半，並捨棄其中一半。
常見錯誤：學生常忘記二分搜尋要求清單必須先排序！
4. 比較線性搜尋與二分搜尋
電腦什麼時候該使用哪種方法？這完全取決於清單是否已排序，以及清單的大小。
主要差異與效率
效率 (Efficiency) 指的是演算法運行的速度，特別是隨著資料清單大小的增加。
線性搜尋：
- 適用於：未排序或已排序的資料。
- 效率：低（慢）。在最壞的情況下，如果清單有 N 個項目，最多需要 N 個步驟。
- 何時使用：當清單較小，或者資料未經排序且你沒有時間先進行排序時。
二分搜尋：
- 適用於：僅限已排序的資料。
- 效率：高（非常快）。每一步都將剩餘資料減半，這意味著它需要的步驟比清單大小少得多。
- 何時使用：當清單非常大且資料已經排序時（或者值得花時間先排序時）。
你知道嗎？如果你有 1,000,000 個項目的清單，線性搜尋可能需要進行 1,000,000 次檢查，而二分搜尋僅需要大約 20 次檢查！這就是巨大的速度差異！
總結表：選擇正確的搜尋方式
| 特性 | 線性搜尋 | 二分搜尋 | |---|---|---| | 資料要求 | 未排序或已排序 | 必須已排序 | | 最壞情況速度 | 慢（檢查每個項目） | 非常快（每次對半砍） | | 實作難度 | 程式碼簡單 | 程式碼較複雜 |
最終重點：搜尋演算法
如果你需要搜尋一個大型的已排序清單，二分搜尋是速度冠軍。如果你的清單很小，或者資料雜亂且未經排序，線性搜尋是確保你能找到項目的唯一選擇。