Searching algorithms

歡迎來到搜尋演算法的世界！

你好！在這一章中，我們將深入探討電腦科學家必備的最基本技能之一：如何快速地找到目標。無論你是要在巨大的資料庫中進行搜尋，還是要在手機通訊錄中尋找聯絡人，搜尋演算法都在幕後發揮著重要的作用。

我們將探討兩種主要的搜尋演算法：直觀（但速度較慢）的線性搜尋 (Linear Search) 以及巧妙（但有前提條件）的二分搜尋 (Binary Search)。理解這些演算法能幫助你編寫出更高效、更聰明的程式。如果一開始覺得有點難也不用擔心——我們會運用大量的類比來拆解這些概念！

3.4.1 搜尋演算法

1. 線性搜尋演算法（慢但可靠的方法）

線性搜尋（或稱順序搜尋）是在列表或陣列中尋找項目最簡單的方法。它的運作方式正如其名：從列表的開頭開始，直線地逐一檢查每個項目，直到找到目標為止。

線性搜尋的運作原理（步驟教學）

想像你面前有一排沒有標籤的儲物櫃，而你正在尋找 42 號儲物櫃。你會從第一個櫃子開始，一個接一個地檢查，直到找到 42 號為止。

1. 從列表的最開頭（索引 0）開始。
2. 檢查當前的項目。
3. 這個項目是你正在尋找的目標嗎？
   • 如果是「是」，則停止搜尋並返回該位置（索引）。任務完成！
   • 如果是「否」，則移動到列表中的下一個項目。
4. 如果你到達了列表的末端卻仍未找到該項目，則代表該項目不存在。

線性搜尋的關鍵特性

• 順序不重要：列表不需要經過排序。這是一個巨大的優勢！
• 實作：此演算法非常容易編寫，通常只需一個簡單的迴圈（迭代）即可完成。
• 效率（時間）：在最壞的情況下，你必須檢查列表中的每一個項目。如果列表有 $N$ 個項目，你最多可能需要進行 $N$ 次檢查。這在效率上被描述為 $O(n)$（線性時間）。

你知道嗎？（效率小撇步）

雖然基礎版的線性搜尋會檢查每個項目，但一個高效的版本會在找到項目後立即停止。如果目標恰好是第一個項目，搜尋瞬間即可完成！如果目標是最後一個項目，或者根本不存在，搜尋才會花費最長的時間。

2. 二分搜尋演算法（快但挑剔的方法）

二分搜尋演算法速度驚人，但它有一個至關重要的規則：列表或陣列必須已經排序 (Sorted)。如果資料不是按順序排列的（例如按數字大小或字母順序），二分搜尋將無法正確運作。

二分搜尋使用了一種強大的策略，稱為分治法 (Divide and Conquer)。它不是一次檢查一個項目，而是在每個步驟中排除掉剩餘資料的一半。

類比：查字典

想像你在查閱一本厚重的紙本字典（字典總是有序的！）。

你不會從第 1 頁開始翻。你會大約從中間打開。如果目標單字以「S」開頭，而中間頁面是「K」，你可以立即拋棄整本書的前半部分！然後，你對剩下的部分重複此過程，不斷地將搜尋範圍減半。

二分搜尋的運作原理（步驟教學）

我們使用三個指標來追蹤搜尋範圍：Low (下界)、High (上界) 和 Mid (中間)。

1. 確保列表已排序。
2. 將 Low 指標設為列表的開頭（索引 0）。
3. 將 High 指標設為列表的結尾（索引 $N-1$）。
4. 當 Low 小於或等於 High 時：
   1. 計算 Mid 點：$Mid = (Low + High) / 2$（向下取整）。
   2. 將 Mid 位置的項目與目標 (Target) 進行比較：
   • 若 $List[Mid] = Target$：成功！返回 Mid。
   • 若 $List[Mid] < Target$：目標必定在後半部分。移動 Low 指標：$Low = Mid + 1$。
   • 若 $List[Mid] > Target$：目標必定在前半部分。移動 High 指標：$High = Mid - 1$。
5. 如果迴圈結束仍未找到目標，則代表該項目不存在。

追蹤範例

在列表 [10, 20, 30, 40, 45, 50, 60, 70]（8 個項目）中搜尋目標 45

第一輪：

• Low = 0, High = 7
• Mid = (0 + 7) / 2 = 3。$List[3]$ 是 40。
• 45 > 40。目標較大，排除前半部分。
• 新的 Low = $Mid + 1 = 4$。（新範圍：[45, 50, 60, 70]）

第二輪：

• Low = 4, High = 7
• Mid = (4 + 7) / 2 = 5。$List[5]$ 是 50。
• 45 < 50。目標較小，排除後半部分。
• 新的 High = $Mid - 1 = 4$。（新範圍：[45]）

第三輪：

• Low = 4, High = 4
• Mid = (4 + 4) / 2 = 4。$List[4]$ 是 45。
• 45 = 45。找到了！

只花了 3 次檢查就找到了目標！而線性搜尋則需要 5 次檢查。

二分搜尋的效率

二分搜尋在時間效率上極高。每次比較都會將搜尋空間減半。對於一個有 $N$ 個項目的列表，檢查次數最多與 $N$ 的對數成正比。這被記作 $O(\log n)$。

範例：如果你有 100 萬個項目（$N=1,000,000$），線性搜尋可能需要 100 萬次檢查。而二分搜尋最多只需 20 次檢查！

3. 比較搜尋演算法

在選擇演算法時，我們主要根據兩個準則進行比較：效率（速度有多快）和條件（資料必須處於什麼狀態）。

比較表

特性	線性搜尋	二分搜尋
前提條件	列表可以是無序的。	列表必須是有序的。
時間效率（最壞情況）	$O(n)$（線性時間）	$O(\log n)$（對數時間）
運作方式	順序檢查每一個項目。	重複將資料範圍減半。
應用場景	小型列表，或變動頻繁、難以保持排序的列表。	非常巨大、穩定且已排序的資料集（如資料庫）。

理解時間效率

在 AS 水平，你需要具備比較時間效率的能力，而不僅僅依賴於大 O 符號。

• 線性搜尋：如果你將列表大小翻倍（從 10 個項目增加到 20 個），搜尋時間大約會翻倍。時間隨列表大小的增加呈線性增長。
• 二分搜尋：如果你將列表大小翻倍，搜尋時間只會增加一個步驟（多一次減半運算）。時間隨列表大小的增加而增長得非常、非常緩慢。

結論：對於大型資料集而言，儘管初始需要花費時間對列表進行排序（如果尚未排序的話），這通常是非常值得的，因為二分搜尋的速度比線性搜尋快得多。