練習題

基礎題¶

1. 穩定排序和不穩定排序的差異是什麼？在哪些情境下「穩定」會有差？

2. 為什麼「先排序、再搜尋」通常比每次線性掃描更有效率？

3. 二分搜尋和穩定排序之間有什麼依賴關係？能不能先搜尋再排序？

4. 二分搜尋有一個必要前提，你知道是什麼嗎？如果資料還沒排序就直接套用，會發生什麼事？

5. 資料量 1,000,000 筆時，線性搜尋最壞需要幾步？二分搜尋最壞需要幾步？

實作題¶

1. 為 stable_sort 增加一個多鍵排序版本：先按欄位 A 排序，A 相同時再按欄位 B 排序。

2. 修改 binary_search，新增一個 find_leftmost 模式：找到目標後繼續往左擴展，回傳最左側的索引。

3. 為 binary_search 增加一個 find_all 模式：找到目標後，繼續往左右擴展，回傳所有相同值的索引清單。

4. 實作一個 multi_key_sort 函式，支援依多個欄位依序排序（例如先按部門、再按姓名），且每層都能獨立指定升冪或降冪。

反思題¶

• 你正在維護一份每週更新的報名清單，需要反覆查詢特定姓名。你會選擇每次線性搜尋，還是先排序再二分搜尋？決策的關鍵因素是什麼？

• Python 的 sorted() 使用 Timsort，它在「幾乎已排好的資料」上特別快。你能想到什麼實際工作情境，資料幾乎已經排好了？

• 本章的 binary_search 在找到第一個匹配值時就停下來。如果資料有重複值，你希望它回傳最左邊的那筆，還是任意一筆？這個決定對下游邏輯有什麼影響？