本章目標理解排序與搜尋在日常資料處理中的核心角色
了解穩定排序的意義，以及何時必須在意它
比較線性搜尋與二分搜尋的效率差異，並知道使用前提
用 Python 建立可重現的排序與搜尋流程，並透過測試確認結果穩定
情境與限制情境：你必須從大量紀錄中找到特定項目，或把資料依某些關鍵欄位排列
輸入：結構化資料表、清單、查詢值
輸出：排序後結果、搜尋索引或搜尋位置
限制：資料可能有重複值、欄位格式不一致、需要保持穩定性
可重現規則本章程式碼位置：
examples/ch03/本章核心模組：
examples/ch03/sorting_search.py測試：
pytest -q tests/test_ch03_sorting_and_searching.py資料：
data/synthetic/（可用scripts/make_synthetic_data.py擴充）
為什麼「先排序、再搜尋」是一個習慣，不只是技巧¶
找不到資料，很多時候不是因為資料不在，而是因為根本沒有整理好。
假設你手上有一份 500 人的活動報名清單，你想確認「王小明」有沒有報名。如果名單沒有排序，你只能一筆一筆看，最壞的情況要掃完整份清單才能確認。但如果名單按姓名排好，你可以直接跳到中間，根據比較結果往前或往後縮小範圍——每一步都能排除一半的資料。
這就是排序和搜尋常常要放在一起看的原因：先整理，再找，速度和穩定性都會提升。
穩定排序：同樣的資料，每次排出同樣的順序¶
排序有一個容易忽略的細節：當兩筆資料的排序鍵相同時，它們的相對順序會不會改變？
穩定排序（stable sort）：相同鍵的資料，原始順序會被保留
不穩定排序（unstable sort）：相同鍵的資料，順序可能每次不同
為什麼這件事重要？
| 情境 | 穩定排序的意義 |
|---|---|
| 報表輸出 | 同部門的人按照原始名單順序排，結果可預測 |
| 待辦排序 | 相同優先度的任務保留原本輸入順序，不會每次亂跳 |
| 資料合併 | 合併後的名單順序一致，方便覆核 |
Python 的 sorted() 和 list.sort() 都是穩定排序（使用 Timsort），所以本章直接用它們，而不需要另外實作。
# 按姓名排序，大小寫不敏感
sorted_list = sorted(names, key=str.lower)
# 相同優先度的任務，保留原始輸入順序
sorted_tasks = sorted(tasks, key=lambda t: t["priority"], reverse=True)線性搜尋 vs 二分搜尋：效率差距有多大¶
搜尋資料有兩種基本方法，效率差距在資料量一大時非常明顯：
| 方法 | 前提 | 時間複雜度 | 適用情境 |
|---|---|---|---|
| 線性搜尋 | 無需排序 | O(n)：最壞要掃完全部 | 資料量小、沒有排序、一次性查詢 |
| 二分搜尋 | 資料必須已排序 | O(log n)：每次砍半 | 資料量大、已排序、需要重複查詢 |
O(log n) 有多快？用具體數字感受一下：
| 資料筆數 | 線性搜尋最壞次數 | 二分搜尋最壞次數 |
|---|---|---|
| 100 | 100 | 7 |
| 10,000 | 10,000 | 14 |
| 1,000,000 | 1,000,000 | 20 |
百萬筆資料，二分搜尋最多只需要 20 步。代價是：資料必須事先排好。
所以決策邏輯是：
只查一次？→ 不值得排序，直接線性搜尋
要查很多次？→ 先排序一次，之後每次都用二分搜尋
二分搜尋的運作邏輯¶
二分搜尋每一步都把搜尋範圍砍半：
先取中間那筆資料
如果中間值等於目標 → 找到，回傳位置
如果中間值小於目標 → 目標在右半邊，左邊界往右移
如果中間值大於目標 → 目標在左半邊，右邊界往左移
重複直到找到或範圍為空（回傳 -1）
用 [1, 3, 5, 7, 9] 搜尋 5 為例：
| 步驟 | 左 | 右 | 中間索引 | 中間值 | 動作 |
|---|---|---|---|---|---|
| 1 | 0 | 4 | 2 | 5 | 找到！回傳 2 |
用同一份清單搜尋 2 為例：
| 步驟 | 左 | 右 | 中間索引 | 中間值 | 動作 |
|---|---|---|---|---|---|
| 1 | 0 | 4 | 2 | 5 | 5 > 2，右邊界移到 1 |
| 2 | 0 | 1 | 0 | 1 | 1 < 2，左邊界移到 1 |
| 3 | 1 | 1 | 1 | 3 | 3 > 2，右邊界移到 0 |
| 4 | 左 > 右 | — | — | — | 範圍空了，回傳 -1 |
實作範例¶
請參考 examples/ch03/sorting_search.py。請在專案根目錄執行程式，以確保路徑正確。
from examples.ch03.sorting_search import stable_sort, binary_search
# 穩定排序：大小寫不敏感
names = ["b", "A", "c"]
print(stable_sort(names, key=str.lower))
# ["A", "b", "c"] ← A 雖然是大寫，但排在最前（str.lower 後是 "a"）
# 二分搜尋：找到時回傳索引，找不到時回傳 -1
items = [1, 3, 5, 7, 9]
print(binary_search(items, 5)) # 2
print(binary_search(items, 2)) # -1
# 支援自訂 key：大小寫不敏感搜尋
words = ["apple", "banana", "cherry"]
print(binary_search(words, "Banana", key=str.lower)) # 1示範流程包含：
用穩定排序整理清單，支援自訂排序鍵
透過二分搜尋加快定位速度，支援相同 key 函式
處理重複值（回傳第一個找到的位置）與查無資料（回傳 -1）
用測試確認排序結果與搜尋位置的穩定性