歡迎來到搜尋與排序的世界！
你有沒有想過，Google 如何在幾毫秒內從數十億個網頁中找到特定結果？或者，當你在手機通訊錄新增一個名字時，它又是如何瞬間自動完成字母排序的？這就是搜尋與排序演算法 (Searching and Sorting Algorithms) 的威力。在本章中，我們將學習電腦如何有效率地組織資料並找到所需的資訊。別擔心步驟看起來很多——只要把它們想像成處理資料的「食譜」。一旦你掌握了這些「食材」，所有的步驟都會變得非常合情合理！
1. 搜尋演算法
搜尋是指在資料集合中找到特定項目（稱為目標值，target）的過程。在課程大綱中，我們主要聚焦於兩種方法：線性搜尋 (Linear Search) 與 二分搜尋 (Binary Search)。
線性搜尋 (Linear Search)
這是尋找目標最直接的方法。你從清單的最開頭開始，逐一檢查每一個項目，直到找到目標或者到達清單末端為止。
生活類比： 想像你在電影院的一排座位中找朋友。你從 1 號位開始，盯著每個人的臉看，直到看到你的朋友為止。
運作方式（步驟說明）：
1. 從第一個元素（索引值 0）開始。
2. 將目前元素與目標值進行比較。
3. 如果兩者相符，恭喜你！你找到了。
4. 如果不符，移動到下一個元素。
5. 重複以上動作，直到找到目標或遍歷完所有項目。
快速複習： 線性搜尋適用於任何清單，無論該清單是否有經過排序！
二分搜尋 (Binary Search)
二分搜尋的速度快得多，但它有一條嚴格的規定：清單必須先經過排序！ 它採用的是「分治法 (divide and conquer)」策略。
生活類比： 試想一本實體字典。如果你要查 "Marmalade"，你絕對不會從第 1 頁開始翻。你會直接翻到中間，如果你看到 "P"，你就知道 "M" 一定在前半部。你在一秒鐘內就排除了整本字典的一半內容！
運作方式（步驟說明）：
1. 找出目前清單的中間元素。
2. 如果中間元素就是目標值，搜尋結束！
3. 如果目標值小於中間值，捨棄右半部，在左半部重複搜尋。
4. 如果目標值大於中間值，捨棄左半部，在右半部重複搜尋。
5. 持續進行分割，直到找到目標項目，或是該「半部」範圍變為空為止。
常見錯誤： 在建議使用二分搜尋前，忘了檢查清單是否已排序。如果清單是無序的，二分搜尋將會失效！
重點總結： 對於小型或未排序的清單，使用線性搜尋；對於大型且已排序的清單，請務必使用二分搜尋以節省時間。
2. 排序演算法
排序是指將資料按特定順序（如字母順序或數字大小）排列的過程。我們將探討四種不同的排序「食譜」。
氣泡排序 (Bubble Sort)
在氣泡排序中，最大的數值會透過重複的交換過程，像氣泡一樣逐漸「浮」到清單的末端。
過程： 比較兩個相鄰的項目。如果順序不對，就交換它們。對整個清單反覆進行此動作，直到不需要再進行交換為止。
你知道嗎？ 氣泡排序通常被認為是最容易編寫的演算法，但在處理大量資料時，它的速度也是最慢的之一。
插入排序 (Insertion Sort)
插入排序是一次一個地建立已排序的清單。它會選取一個未排序的項目，並將其「插入」到已排序項目中的正確位置。
生活類比： 想像你在整理一副撲克牌。你一次拿起一張牌，然後將它滑入手中現有牌組的正確位置。
運作方式： 從第二個項目開始。將其與左邊的項目進行比較。持續向左移動，直到它遇到比自己小的項目或是到達清單開頭為止。
合併排序 (Merge Sort)
合併排序是一種遞迴 (recursive) 演算法，它遵循「分治法 (Divide and Conquer)」原則。
運作方式：
1. 分割 (Divide)： 反覆將清單對半分，直到每個子清單只剩下 1 個項目。
2. 征服 (Conquer)： 只有 1 個項目的清單預設為「已排序」。
3. 合併 (Combine)： 將這些小清單按正確順序合併回去，直到恢復成一個完整的已排序大清單。
快速排序 (Quicksort)
快速排序同樣使用「分治法」，但它聚焦於一個基準值 (pivot)。
運作方式：
1. 選擇一個項目作為基準值（通常選第一個或最後一個）。
2. 分割 (Partitioning)： 將所有比基準值小的項目移到左邊，比基準值大的移到右邊。
3. 此時，基準值已處於最終且正確的位置！
4. 對左右兩邊重複上述過程，直到整個清單完成排序。
重點總結： 氣泡與插入排序簡單但處理巨量資料時很慢。合併排序與快速排序較複雜，但在處理大型清單時，因其較優異的效率而更受歡迎。
3. 演算法效率（Big-O 符號）
我們該如何比較演算法的好壞？我們會使用 Big-O 符號 (Big-O Notation)。它衡量的是最差情況的時間複雜度 (worst-case time complexity)——簡單來說，當資料量 (\(n\)) 增加時，演算法所需的時間會增加多少？
「速度」等級（由快到慢）：
• \(O(1)\) - 常數時間： 無論 \(n\) 的大小如何，耗時始終相同。
• \(O(\log n)\) - 對數時間： 非常快！隨著 \(n\) 的增加，時間增長緩慢（例如：二分搜尋）。
• \(O(n)\) - 線性時間： 時間隨著資料量等比例增長（例如：線性搜尋）。
• \(O(n \log n)\) - 線性對數時間： 對於排序而言相當有效率（例如：合併排序）。
• \(O(n^2)\) - 平方時間： 處理大量資料時很慢。如果將資料量加倍，所需時間會變成原來的四倍（例如：氣泡排序）。
最差情況複雜度比較表：
線性搜尋： \(O(n)\)
二分搜尋： \(O(\log n)\)
氣泡排序： \(O(n^2)\)
插入排序： \(O(n^2)\)
快速排序： \(O(n^2)\)（註：這是當每次選擇的基準值都很差時會發生的情況！）
合併排序： \(O(n \log n)\)
記憶小撇步： 把 Big-O 想像成一種「保證」。如果一個演算法是 \(O(n)\)，電腦保證在最糟糕的情況下，其執行時間也不會超過與資料量成線性關係的時間。
快速複習箱：
• 搜尋： 二分搜尋比線性搜尋快，但需要資料已排序。
• 排序： 在最差情況下，合併排序通常是最穩定的速度選擇 (\(O(n \log n)\))。
• 複雜度： \(O()\) 括號裡面的值越小，代表演算法越好、越快！
總結
搜尋與排序是高效程式設計的基石。線性搜尋是你的「逐一檢查」工具，而二分搜尋則是你的「對半拆解」工具。在排序方面，氣泡排序和插入排序非常適合作為學習基礎與處理小型清單，但合併排序與快速排序因其更佳的 Big-O 效能，成為實際軟體開發中的主力。繼續練習這些步驟，你很快就會成為演算法專家！