歡迎來到搜尋演算法的世界！
你有沒有試過在龐大的播放清單中尋找一首特定的歌曲，或者在電話簿中找某一個名字？如果有，那你其實已經執行過一次搜尋（Search）了！在電腦科學中，搜尋就是從資料集合（如列表或陣列）中找出特定資料的過程。
不用擔心「演算法」聽起來很嚇人——它們其實就只是一組用來完成任務的「指令集」。今天，我們要來看看電腦尋找目標時最主要的兩種方式：線性搜尋（Linear Search）和二元搜尋（Binary Search）。
1. 線性搜尋：逐一檢查法
線性搜尋是最簡單的搜尋方法。它會從列表的最開頭開始，逐一檢查每一個項目，直到找到目標或檢查完所有項目為止。
運作原理（機制）：
想像你面前有一排五個封閉的盒子，你要尋找裡面隱藏的金幣。
1. 打開第一個盒子。裡面有金幣嗎？如果有，停止！如果沒有，繼續下一個。
2. 打開第二個盒子。裡面有金幣嗎？如果沒有，繼續下一個。
3. 依此類推，持續檢查第三、第四和第五個盒子，直到找到金幣或盒子全數打開為止。
現實生活中的例子：
在凌亂、未整理的抽屜裡找一雙特定的襪子。你必須一隻一隻地把襪子拿出來看，直到找到正確的那一雙為止。
快速重溫：線性搜尋的優缺點
優點：
• 非常容易理解和編寫程式。
• 適用於任何列表，無論項目是有序排列（已排序）還是完全混亂（未排序）。
缺點：
• 對於大型列表來說，它非常慢。如果你有 1,000,000 個項目，而你要找的那個剛好在最後面，電腦就必須進行 1,000,000 次檢查！
重點提醒： 當列表很小，或者列表沒有經過排序時，使用線性搜尋最合適。
2. 二元搜尋：分治法（Divide and Conquer）
二元搜尋快得多，但它有一個非常重要的前提規則：列表必須是已排序的（例如：按字母順序排列，或是由小到大的數字排列）。
運作原理（機制）：
二元搜尋不是從開頭開始，而是直接跳到列表的中間。
1. 查看已排序列表的中間項目。
2. 這是你要找的項目嗎？如果是，那就完成了！
3. 你的目標比中間項目小嗎？如果是，就捨棄列表的右半部分。
4. 你的目標比中間項目大嗎？如果是，就捨棄列表的左半部分。
5. 對剩下的那一半重複此過程，直到找到目標為止。
你知道嗎？
二元搜尋的效率高得驚人。即使你要在全世界所有人（約 80 億人）的名單中進行搜尋，二元搜尋也只需約 33 個步驟就能找到特定名字！
現實生活中的例子：
想像一下在字典裡找一個詞。你不會從第 1 頁開始翻，你會從中間打開。如果目標詞彙在當前頁面之後，你就忽略字典的前半部分，只在後半部分搜尋。
快速重溫：二元搜尋的優缺點
優點：
• 對於大量數據來說，速度極快。
• 每進行一次檢查，你就能刪除剩餘數據中一半的範圍。
缺點：
• 它只適用於已經排序過的列表。如果列表很雜亂，演算法就會失效。
重點提醒： 二元搜尋是處理大數據的「速度之王」，但你必須先將列表排序！
3. 兩者比較：哪一個更好？
在考試中，你可能會被要求比較這兩種方法。這裡有一份實用的指南幫助你選擇：
1. 列表是否需要已排序？
• 線性搜尋：不需要。
• 二元搜尋：需要。
2. 速度如何？
• 線性搜尋：慢（特別是對於長列表）。
• 二元搜尋：快（特別是對於長列表）。
3. 我應該在什麼時候使用？
• 線性搜尋：當列表很小或未排序時。
• 二元搜尋：當列表很大且已經排好序時。
記憶小技巧：「線性」法
要記住線性搜尋（Linear Search），想像排成一線（Line）的人群。為了找到某個人，你必須沿著隊伍走，逐一檢查每一個人。
應避免的常見錯誤
• 錯誤： 以為二元搜尋適用於任何列表。
修正：在建議使用二元搜尋之前，務必先檢查列表是否已排序！
• 錯誤： 認為線性搜尋因為比較慢所以很「糟糕」。
修正：如果列表非常小，或者數據變動太頻繁，以至於排序所需的成本過高，那麼線性搜尋其實是更好的選擇。
快速複習測驗（心智檢查！）
1. 哪種搜尋演算法會從第一個項目開始？（答案：線性搜尋）
2. 在使用二元搜尋之前，列表必須具備什麼條件？（答案：必須是已排序的）
3. 如果你有一個包含 10 個項目的列表，哪種搜尋方式比較簡單？（答案：線性搜尋）
4. 如果你在 1,000,000 個已排序的項目中進行搜尋，哪種方法比較快？（答案：二元搜尋）
如果起初覺得這些概念有點難懂也別擔心！只要記住：線性 =「逐一搜尋」，二元 =「對半分割」。你一定行的！