歡迎來到搜尋演算法的世界！
你好！在這一章節中，我們將探討電腦如何在龐大的數據集中找到特定資訊。無論你是要在手機中搜尋聯絡人，還是在 Google 上尋找網頁，背後都有搜尋演算法在運作。針對 AQA A Level 課程，我們需要掌握三種主要方法：線性搜尋 (Linear Search)、二分搜尋 (Binary Search) 和 二元樹搜尋 (Binary Tree Search)。別擔心這些名詞看起來很複雜，我們會一步一步為你拆解！
1. 線性搜尋：逐一檢查法
線性搜尋是找到目標最簡單的方法。想像你有一堆混亂的襪子，正在尋找那隻有圓點圖案的。你會拿起第一隻檢查，看過後放下，再拿起第二隻，以此類推，直到找到正確的那一隻為止。
運作原理（步驟說明）：
1. 從列表的最開頭（索引 0）開始。
2. 將當前的項目與你要搜尋的目標進行比較。
3. 如果兩者相符，恭喜！你找到了。
4. 如果不符，移動到列表中的下一個項目。
5. 重複以上步驟，直到找到目標或檢查完列表中的所有項目。
複雜度與效率
在計算機科學中，我們使用 Big O 符號 (Big O notation) 來描述演算法的快慢。線性搜尋的時間複雜度為 \(O(n)\)。
為什麼呢？ 因為在最壞的情況下（即目標項目位於列表末尾，甚至根本不在列表中），你必須檢查列表中的每一個項目（共 \(n\) 個）。
小貼士：線性搜尋是此處唯一適用於未排序數據的演算法。如果你的列表完全沒有整理過，線性搜尋就是你唯一的選擇！
重點總結：
線性搜尋編寫代碼簡單，但對於大量數據來說效率較慢。其時間複雜度為 \(O(n)\)。
2. 二分搜尋：分治法
二分搜尋的速度要快得多，但它有一個非常重要的規則：數據必須已經過排序（例如按字母順序或數字大小排列）。如果列表未經排序，二分搜尋將無法運作！
比喻： 想像你在實體字典中查單字。你不會從第 1 頁開始翻，而是打開中間，看看你要找的字是在那一頁之前還是之後，然後直接捨棄掉那一半你不需要的部分。
運作原理（步驟說明）：
1. 找到列表的中間元素。
2. 將中間元素與你的目標進行比較。
3. 如果目標等於中間元素，你就完成了！
4. 如果目標小於中間元素，捨棄列表的右半部分。
5. 如果目標大於中間元素，捨棄列表的左半部分。
6. 對剩餘的部分重複此過程，直到找到目標為止。
複雜度與效率
由於你每次都在減半搜尋範圍，這個演算法的速度非常快。其時間複雜度為 \(O(\log n)\)。
常見錯誤： 忘記列表必須先排序。在考試中，如果題目要求你對一個未排序的列表執行二分搜尋，你的第一步必須先說明需要先對列表進行排序！
重點總結：
二分搜尋對於大型數據集非常有效，但前提是數據必須已排序。其時間複雜度為 \(O(\log n)\)。
3. 二元樹搜尋
二元樹搜尋涉及在二元搜尋樹 (BST) 中進行搜尋。在這種結構中，每個「節點 (node)」都有一個值，並且最多可以有兩個「子節點」（左和右）。
BST 的黃金法則：
對於樹中的任何節點：
- 小於該節點的值會放在左邊。
- 大於該節點的值會放在右邊。
記憶法： Left is Less！（左邊就是比較小的！）
如何搜尋二元樹（步驟說明）：
1. 從根節點 (Root)（最頂端的節點）開始。
2. 根節點是你想要的值嗎？如果是，停止！
3. 你的目標是否小於當前節點？如果是，移動到左側子節點。
4. 你的目標是否大於當前節點？如果是，移動到右側子節點。
5. 重複上述步驟，直到找到目標值，或者遇到「null」（空值），這意味著該值不在樹中。
複雜度與效率
就像二分搜尋一樣，如果樹是平衡的，你本質上是在每一步將需要檢查的節點數量減半。因此，時間複雜度為 \(O(\log n)\)。
你知道嗎？ 如果二元樹非常「不平衡」（例如每個節點都只有右子節點），它基本上就變成了一個列表，搜尋速度會退化回 \(O(n)\)！
重點總結：
二元樹搜尋使用分支結構來尋找數據。只要樹保持平衡，其時間複雜度通常為 \(O(\log n)\)。
快速複習表
演算法：線性搜尋
是否需要數據排序？ 否
時間複雜度： \(O(n)\)
演算法：二分搜尋
是否需要數據排序？ 是
時間複雜度： \(O(\log n)\)
演算法：二元樹搜尋
是否需要數據排序？ 不適用（數據已在樹結構中組織）
時間複雜度： \(O(\log n)\)
總結：我該選哪一個？
1. 如果數據量很小或未排序，請使用線性搜尋。
2. 如果數據量很大且已在陣列中排序完畢，請使用二分搜尋。
3. 如果你需要頻繁地添加和移除項目，同時還要保持搜尋功能，那麼二元樹通常是最好的選擇。
如果剛開始覺得這些概念很棘手，別擔心！最好的學習方法是嘗試畫出一組數字，並用手指模擬二分搜尋的步驟。你會發現搜尋範圍縮小的速度有多快！