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

你有沒有試過在書包裡翻來覆去只為了找一枝筆，或者在字典裡快速查一個生字？如果有的話，其實你已經在日常生活中運用了搜尋策略！在電腦科學中，我們把這些逐步解決問題的方法稱為搜尋演算法（Searching Algorithms）。

即使一開始覺得有點抽象也不用擔心。讀完這份學習筆記後，你將會完全明白電腦是如何尋找資料、它們常用的兩種主要搜尋方法，以及如何針對不同情況選擇最佳的演算法。

1. 關鍵詞彙與核心概念

在深入探討之前，讓我們先認識幾個基本概念：

• 演算法（Algorithm）： 一組用來解決問題或完成特定任務的逐步、精確且明確的指令。
• 搜尋演算法（Searching Algorithm）： 一種有系統的計算方法，用來在資料集（例如清單）中找出特定項目，或者確認該項目並不存在。
• 目標（Target 或 Search Key）： 你正在尋找的特定數值或項目。
• 元素（Element 或 Item）： 清單內的個別數值。
• 索引（Index）： 項目在清單中的位置編號。
• 比較（Comparison）： 電腦將目標值與清單中的項目進行核對，以判斷兩者是相等、較小還是較大的操作。
• 效率（Efficiency / Utility）： 演算法找到目標項目所需進行的比較次數，特別是在清單資料量變大時的表現指標。

重點提示： 每當電腦搜尋資料時，它都會遍歷清單並不斷進行比較，直到找到目標或檢查完所有項目為止。

想像一下在一副洗亂了的撲克牌中尋找一張特定的牌。你會從第一張開始看，然後看第二張、第三張，依序逐張檢查，直到找到你要的牌為止。

這正是線性搜尋（又稱順序搜尋）的運作方式！

線性搜尋的逐步運作流程

1. 從清單的第一個元素（位置 1 或索引 0）開始。
2. 將當前元素與你的目標進行比較。
3. 如果兩者吻合，搜尋立即停止：顯示「已找到！」並回報其位置。
4. 如果兩者不吻合，便移向清單中的下一個項目。
5. 重複步驟 2 至 4，直到找到該項目，或者檢查至清單末端仍未發現吻合項目為止（顯示「找不到」）。

追蹤範例

讓我們在這個未排序的清單中尋找目標數值 7：[4, 9, 7, 2]
• 步驟 1： 檢查位置 1（數值：4）。\(4 = 7\) 嗎？不是。移至下一個。
• 步驟 2： 檢查位置 2（數值：9）。\(9 = 7\) 嗎？不是。移至下一個。
• 步驟 3： 檢查位置 3（數值：7）。\(7 = 7\) 嗎？是的！在位置 3 找到目標項目。

線性搜尋的效能

設 \(n\) 為清單中的項目總數。
• 最佳情況（Best-Case Scenario）： \(1\) 次比較（目標項目剛好在最開頭）。
• 最差情況（Worst-Case Scenario）： \(n\) 次比較（目標項目在最後一個位置，或者根本不在清單中）。
• 平均情況（Average-Case Scenario）： 大約 \(\frac{n}{2}\) 次比較。

優點與缺點

• 優點： 適用於任何清單，無論資料是否已經排序。
• 優點： 概念非常簡單，容易理解和編寫程式。
• 缺點： 處理大型清單時非常緩慢且效率低（搜尋 1,000,000 個項目可能需要高達 1,000,000 次比較！）。

重點提示： 線性搜尋由頭到尾逐一檢查項目。它不需要預先排序，但在資料量龐大時速度會變得很慢。

3. 二分搜尋（Binary Search / Divide and Conquer）

想像一下猜一個介乎 1 到 100 之間的秘密數字。如果你猜 50，而對方說「太大」，你就可以立刻排除 50 到 100 的所有數字！只需猜一次，你就把搜尋範圍縮小了一半。

這就是二分搜尋（Binary Search，又稱折半搜尋）的威力。

二分搜尋的黃金法則

關鍵條件： 資料必須已排序（按數值大小或字母順序排列）。如果清單未經排序，二分搜尋將完全無法運作！

二分搜尋的逐步運作流程

1. 設定兩個指標來標示搜尋範圍：start（起始位置）和 end（結束位置）。
2. 利用整數除法計算出中間位置：
\(\text{mid} = \lfloor(\text{start} + \text{end}) / 2\rfloor\)
3. 將中間元素與目標進行比較：
• 如果中間元素等於目標：找到了！搜尋結束。
• 如果目標比中間元素小：捨棄中間項目及整個後半部分，設定 \(\text{end} = \text{mid} - 1\)。
• 如果目標比中間元素大：捨棄中間項目及整個前半部分，設定 \(\text{start} = \text{mid} + 1\)。
4. 在縮小了的子清單中重複步驟 2 和 3，直到找到目標，或者當 start 大於 end 為止（代表清單中「找不到」該項目）。

追蹤範例

讓我們在這個包含 7 個項目的已排序清單中尋找目標數值 19：[3, 6, 8, 12, 15, 19, 24]
• 第 1 輪： \(\text{start} = 1\)，\(\text{end} = 7\)。中間位置為 \(\lfloor(1 + 7) / 2\rfloor = 4\)。位置 4 的元素是 12。
\(19 = 12\) 嗎？不是。由於 \(19 > 12\)，因此排除左半部分！設定 \(\text{start} = 4 + 1 = 5\)。
• 第 2 輪： \(\text{start} = 5\)，\(\text{end} = 7\)。中間位置為 \(\lfloor(5 + 7) / 2\rfloor = 6\)。位置 6 的元素是 19。
\(19 = 19\) 嗎？是的！只需 2 次比較便在位置 6 找到目標項目。

二分搜尋的效能

• 最佳情況： \(1\) 次比較（第一次檢查的中間項目剛好就是目標）。
• 最差情況／平均情況： 大約 \(\log_2(n)\) 次比較。每一次比較都會將剩餘的清單範圍縮小一半！
• 你知道嗎？ 在一個包含 1,000 個項目的已排序清單中，線性搜尋最多可能需要 1,000 步，而二分搜尋最多只需 \(\lceil\log_2(1000)\rceil = 10\) 次比較！

優點與缺點

• 優點： 處理大量數據時極為快速且高效。
• 缺點： 清單必須預先排序。如果清單未經排序，需要額外花時間進行排序。
• 缺點： 演算法的追蹤和編寫比線性搜尋複雜。

重點提示： 二分搜尋透過不斷檢查中間項目，每次將搜尋範圍減半。它的速度飛快，但只適用於已排序的清單。

4. 線性搜尋與二分搜尋的比較

在解決問題時，電腦科學家必須選擇最合適的工具。以下是兩種演算法的對比：

數據要求：
• 線性搜尋： 任何數據集（適用於未排序或已排序的數據）。
• 二分搜尋： 必須已排序（遞增或遞減排序）。

搜尋機制：
• 線性搜尋： 從頭到尾順序逐一檢查項目。
• 二分搜尋： 重複檢查中位數，每次將搜尋範圍減半。

最佳情況比較次數：
• 線性搜尋： \(1\)
• 二分搜尋： \(1\)

最差情況比較次數：
• 線性搜尋： \(n\)（清單中的項目總數）。
• 二分搜尋： \(\log_2(n)\)（向上取整至最接近的整數）。

最佳應用場景：
• 線性搜尋： 項目較少的短清單、未排序的數據，或一次性的快速搜尋。
• 二分搜尋： 龐大的數據集，以及已經排序且需要頻繁搜尋的清單。

5. 應避免的常見錯誤

在作答題目時，請特別留意以下常見陷阱：

1. 在未排序的清單上使用二分搜尋：
錯誤： 嘗試在如 [9, 2, 8, 1] 這樣的未排序清單中執行二分搜尋。
更正： 二分搜尋完全依賴順序。如果清單未排序，隨意捨棄一半的清單可能會不小心把目標項目也一併丟棄！

2. 忘記「最差情況」的真正意思：
錯誤： 以為線性搜尋每一次都必定需要 \(n\) 步。
更正： 線性搜尋只有在最差情況下（即項目在最後一個位置或根本不存在時）才需要 \(n\) 步。如果你運氣好，目標在第一個位置，就只需 \(1\) 步。

3. 中間位置計算錯誤：
錯誤： 當總和除以 2 出現小數時感到混亂。
更正： 務必使用整數除法（無條件捨去小數點，取向下取整值），例如：\(\lfloor(1 + 4) / 2\rfloor = \lfloor 2.5 \rfloor = 2\)。

4. 忽略「找不到項目」的情況：
錯誤： 假設目標項目一定存在於清單中。
更正： 一個完善的演算法必須妥善處理找不到項目的情況（線性搜尋中到達清單末端，或二分搜尋中出現 \(\text{start} > \text{end}\)）。

6. 本章溫習清單

在完成學習前，請確保自己能夠：
• 定義甚麼是搜尋演算法、目標及比較。
• 解釋線性搜尋的逐步運作流程，並能手動追蹤其在清單上的搜尋過程。
• 指出線性搜尋的最佳情況（\(1\)）與最差情況（\(n\)）效能。
• 解釋二分搜尋的逐步運作流程，並懂得利用整數除法計算中間位置。
• 緊記二分搜尋必須在已排序的清單上進行。
• 說明為甚麼在處理龐大數據集時，二分搜尋的效率遠高於線性搜尋。