歡迎來到搜尋演算法的世界！
在電腦科學中，搜尋是最基礎的運作之一。無論你是在手機通訊錄尋找聯絡人、在 YouTube 上找特定影片，還是在資料庫中尋找最高分數，背後都有演算法在幫你找出這些資料。在本章中，我們將探討電腦尋找目標的兩種主要方式：線性搜尋 (Linear Search) 與 二分搜尋 (Binary Search)。
如果一開始覺得「演算法」聽起來很深奧，別擔心！讀完這些筆記後，你會發現它們其實就像我們日常生活中解決問題的方法一樣直觀。
1. 線性搜尋：逐一比對法
線性搜尋是最簡單的搜尋方式。它會從列表的開頭開始，逐一檢查每一個項目，直到找到目標或是到達列表的盡頭為止。
運作流程（步驟教學）：
1. 從列表中的第一個項目開始。
2. 將該項目與你要找的目標（target）進行比較。
3. 如果兩者相符，停止！你已經找到了。
4. 如果不相符，移動到下一個項目。
5. 重複步驟 2-4，直到找到項目或檢查完整個列表。
現實生活中的比喻：
想像你在凌亂的洗衣籃中找一件特定的襯衫。你拿起第一件襯衫，檢查一下，放到旁邊；再拿起第二件，檢查一下，以此類推。這就是線性搜尋的運作方式！
效率小貼士：
課程大綱提到了這種搜尋的兩個版本：
- 無效率版本：演算法即使已經找到目標，仍會繼續檢查剩餘的每一個項目。
- 進階版本：演算法在找到項目後立即停止。這能節省不少時間！
快速回顧：線性搜尋適用於任何列表，無論該列表是已排序（有順序）還是未排序（隨機）。
重點總結：線性搜尋雖然簡單，但在資料量龐大時效率較低，因為在最壞的情況下，你必須檢查每一個項目。
2. 二分搜尋：「分而治之」法
二分搜尋比線性搜尋快得多，但它有一個非常重要的規則：列表必須已經排序（例如：按字母順序排列，或由小到大排列數字）。
運作流程（步驟教學）：
1. 找出列表的中間項目。
2. 將中間項目與你的目標進行比較。
3. 如果中間項目就是目標，恭喜你完成了！
4. 如果你的目標比中間項目小，就捨棄列表的右半部分。
5. 如果你的目標比中間項目大，就捨棄列表的左半部分。
6. 重複上述過程，處理剩餘的部分，直到找到該項目為止。
尋找中間點的數學運算：
要找出中間的索引值（index），我們通常會使用這個簡單的公式：
\( \text{mid} = \text{integer}(\frac{\text{first\_index} + \text{last\_index}}{2}) \)
現實生活中的比喻：
試想在印刷版的字典裡找一個詞。你不會從第 1 頁開始讀每一個詞（那是線性搜尋）。相反地，你會直接翻開中間。如果你想找的詞在中間頁的「前面」，你會忽略整本書的後半部分，只在前半部分繼續尋找。
你知道嗎？二分搜尋非常迅速，即使你面對的是一個擁有 100 萬個項目的列表，最多也只需要 20 個步驟就能找到你的目標！
重點總結：二分搜尋對於處理大量資料極為有效，但前提是資料必須已經排序。
3. 兩種演算法的比較
在考試中，你可能會被要求比較這兩種演算法。以下是一個簡單的對照表，幫助你記住它們的差異：
線性搜尋 (Linear Search)
- 必要條件：無。適用於已排序或未排序的列表。
- 時間效率：對於大型列表較慢。時間消耗隨著項目數量線性增長。
- 最佳使用場景：列表很短，或者資料完全未經排序時。
二分搜尋 (Binary Search)
- 必要條件：資料必須先經過排序。
- 時間效率：非常快。即使列表的大小加倍，也只需要多花一個步驟就能完成搜尋。
- 最佳使用場景：當你擁有一個龐大且已排序的資料集時。
常見的考試陷阱：在考試題目中，千萬不要試圖對「未排序的列表」使用二分搜尋。你必須先聲明該列表需要先進行排序！
記憶技巧與訣竅
- Linear（線性）= Line（隊列）。想像一排人，你要一個一個地檢查他們。
- Binary（二分）= Bi（二）。想像一輛有兩個輪子的腳踏車（Bicycle），你總是將列表分成兩半。
總結檢查清單
- 你能根據一串數字進行線性搜尋的推演嗎？
- 你知道高效的線性搜尋在找到項目後會停止嗎？
- 你能解釋為什麼二分搜尋必須在已排序的列表上執行嗎？
- 你能在二分搜尋的步驟中計算列表的中間點嗎？
- 你能解釋對於 10,000 個已排序的名字列表，哪種演算法更快嗎？（提示：是二分搜尋！）
繼續練習！嘗試畫出一些數字列表，並用筆模擬演算法的操作過程。你很快就會成為高手！