排序與搜尋：演算法入門

💡 先搞懂問題

北辰書店的電腦裡有一份書號清單，顧客問：「有沒有書號 220 的書？在第幾格？」學過第 5 課的串列（list，一排有編號的格子），你知道 220 in codes 會回答 True 或 False，codes.index(220) 會告訴你它在索引幾號。可是電腦並不是「一眼看到」答案，它和人一樣，得照著某一套步驟，一格一格拿出來比。清單只有 6 筆時感覺不出差別；有 100 萬筆時，步驟選得好不好，就是一眨眼和等上好一陣子的差別。

這種「解決某一類問題的明確步驟」叫做演算法（algorithm）。明確的意思是：每一步都清楚到不需要猜、步驟有先後順序、照著做一定會結束，而且會交出結果（包括「找不到」也是一種結果）。程式，就是用電腦看得懂的語言把演算法寫下來。同一個問題常常有好幾種演算法，答案都對，差別在要做多少工作。這一課看三個最經典的：一格一格找的線性搜尋（linear search）、把資料由小到大排好的氣泡排序（bubble sort）、在排好的資料上每次砍掉一半的二分搜尋（binary search）。衡量快慢的方法很直觀：數一數「比較了幾次」。

生活比喻：北辰書店的新店員與步驟卡

北辰書店來了一位新店員，店長給他一張步驟卡。早上書架上的書還沒照書號排，顧客要找 220，步驟卡寫的是：「從最左邊第一本開始，看書背上的書號；是要找的，就回報它在第幾格；不是，就換右邊下一本；整排看完都沒有，就回報『沒有這本』。」最後這一句很重要：步驟卡如果沒寫找不到怎麼辦，新店員走到書架盡頭就不知道該做什麼了。

打烊後，店長要他把書照書號由小到大排好。新店員只會一個簡單動作：比較相鄰的兩本，左邊的號碼比較大就對調。他從最左邊一路比到最右邊，走完一趟，號碼最大的那本就被一次次的對調推到了最右邊；再走一趟，第二大的就到了倒數第二格。走夠趟數，整排就排好了。

隔天書架已經排好，找書就能換個方法：先抽出正中間那一本看書號，要找的號碼比它大，就只看右半排，左半排連看都不用看；比它小就只看左半排。每看一本，剩下要找的範圍就少掉一半。8 本書找 61，從頭找要看 7 本，這個方法只要看 3 本。

演算法要寫成程式之前，最好先確定每一步都沒有模糊地帶。把早上那張找書的步驟卡畫成流程圖，就能一條一條對到程式：「從第一本開始」是 i 從 0 開始，「換下一本」是 i 加 1，「整排看完都沒有」是迴圈結束後還沒找到。

接下來四個實驗室依序是線性搜尋、氣泡排序、二分搜尋三個逐行執行播放器，最後是可以自己輸入資料的比較次數大賽。播放器的格子下方會出現 ▲i、▲j、▲lo 這類橘色標記：它代表那個名字目前貼著的整數被當成索引，正指著哪一格。

🎮 互動實驗室一：一格一格找（線性搜尋）

這段程式就是早上那張步驟卡：在 6 本還沒排序的書號裡找 target。右上角的選單可以切換「找 220（找得到）」和「找 500（找不到）」。按「下一步 ▶」執行一行，看格子下方的 ▲i 一格一格往右移，count 跟著加 1。遇到 🤔 問題時先猜，再按下一步對答案（自動播放也會在這裡停下來）。

🎮 互動實驗室二：氣泡排序，相鄰的比一比、換一換

把 5 本書照書號由小到大排好。▲j 和 ▲j+1 標出這次要比較的相鄰兩格；第 6～8 行用一個暫存的名字 temp 分三步完成交換，被換掉的格子會閃黃色。輸出畫面每一輪印一次串列，可以看到最大的數一輪一輪「浮」到右邊，這也是「氣泡」這個名字的由來。右上角的第二段程式多了一個 swapped：這一輪如果一次都沒有交換，就提早結束。

🎮 互動實驗室三：二分搜尋，每次砍掉一半

二分搜尋只能用在已經排好序的資料上。三個名字 lo、hi、mid 都是索引：lo 和 hi 夾住「答案還可能在的範圍」，mid 是範圍的正中間。右上角可以切換三種情況：找 61、找 79（8 個元素裡比較次數最多的情況）、找 30（找不到）。

🎮 互動實驗室四：比較次數大賽

自己當出題者：輸入一串書號（或按按鈕隨機產生），再輸入要找的書號，按「開始比賽」。上下兩排會同時開始，每一拍各比較一次：線性搜尋從索引 0 一格一格看，二分搜尋每次看範圍的正中間，範圍外的格子會變淡。也可以直接點格子，把那一格的書號當成要找的目標。試試看按「打亂順序」再比一次：資料沒有排好時，二分搜尋會發生什麼事？

📘 原理補完

1. 演算法的正式說法

演算法（algorithm）是「把輸入變成輸出的一串有限、明確的步驟」。以搜尋來說，輸入是一個串列和要找的值，輸出是它的索引，或代表找不到的 -1。判斷一套演算法好不好，依序問三件事：對不對（任何輸入都交出正確結果，包括找不到、串列是空的這些邊緣情況）；會不會結束（迴圈一定有停下來的一天）；要做多少工作。這一課用「比較了幾次」來量工作量，而且最關心的是最壞情況（worst case）：運氣最差的時候要比幾次。進階的教材會用一種叫 Big-O 的記號描述「資料變多時工作量怎麼成長」，現階段用比較次數的直覺就夠了。

2. 線性搜尋：一格一格找，找不到要有交代

線性搜尋（linear search，也叫循序搜尋 sequential search）從索引 0 開始，一格一格拿出來和目標比，相等就停，走到最後都沒有就回報找不到。它的優點是資料不必排序，什麼樣的串列都能用；缺點是最壞情況要把每一格都看過：目標在最後一格或根本不存在時，n 筆資料就要比 n 次。實驗室一的「找 500」就是這種情況，6 筆比了 6 次。

「找不到」要怎麼回報，常見有三種做法：回傳一個不可能是索引的值，例如 -1（第 4 課字串的 find() 就是這樣）；回傳 None；或像串列的 index() 一樣直接丟出錯誤。前兩種的呼叫者要記得檢查回傳值，否則拿 -1 去當索引，會不聲不響地取到最後一格（第 5 課的負索引）。第三種則要先用 in 確認有沒有，或用第 10 課的 try／except 接住。Python 的 x in 串列 和 串列.index(x)，背後做的就是線性搜尋。

3. 氣泡排序：相鄰比較、交換

排序（sorting）是把資料依照某個順序重新排列，最常見的是由小到大，稱為遞增（ascending）。氣泡排序的步驟只有一個動作重複很多次：比較相鄰的兩格 codes[j] 和 codes[j + 1]，左邊比較大就交換。▲j 從最左邊走到右邊叫做一輪（pass），一輪下來，剩下的數裡最大的那一個一定會被一路換到最右邊，因為它和誰比都比較大，每一次都被往右換一格。

既然每一輪都會把剩下最大的放到正確位置，5 個元素只要 4 輪（range(n - 1)），而且第 i 輪（從 0 算起）只要比到還沒排好的部分，也就是 range(n - 1 - i)：第 1 輪比 4 次、第 2 輪 3 次、第 3 輪 2 次、第 4 輪 1 次，一共 10 次。播放器裡的交換分成三步：先用 temp 記住左邊那格，再把右邊的值放到左邊，最後把 temp 放到右邊；少了 temp，左邊原本的值一被蓋掉就找不回來了。Python 也可以用第 2 課學過的寫法一行完成：codes[j], codes[j + 1] = codes[j + 1], codes[j]，右邊先算出兩個值，再同時放回左邊的兩格。不論哪一種，串列是可變物件，交換是就地修改，從頭到尾都是同一個串列。

第 4 輪什麼都沒交換，卻還是比了一次。實驗室二的第二段加上 swapped 記號：一整輪都沒交換，代表每一對相鄰的都已經是小在左、大在右，整個串列排好了，可以 break 提早結束。這種「多記一點資訊，省下沒必要的步驟」的想法，就是改良演算法的典型做法。不過最壞情況（例如資料完全倒過來排）還是要比滿 4 + 3 + 2 + 1 次：n 筆資料是 (n − 1) + (n − 2) + … + 1 次，8 筆是 28 次、100 筆是 4,950 次，資料一多就很吃力。

4. 二分搜尋：lo、mid、hi 每次砍一半

二分搜尋（binary search）的前提是資料已經由小到大排好。它用兩個索引 lo 和 hi 夾住「答案還可能在的範圍」，一開始是整個串列（0 到 len(codes) - 1）。每一圈做三件事：

1. 算出正中間 mid = (lo + hi) // 2。// 是第 3 課的整數除法，小數直接捨去，結果一定是整數，才能當索引。
2. codes[mid] 等於目標：找到了，記下 mid，break。
3. 比目標小：因為資料由小到大排好，mid 和它左邊的每一格都更小，全部丟掉，lo = mid + 1；比目標大：mid 和右邊全部丟掉，hi = mid - 1。

迴圈條件 while lo <= hi 的意思是「範圍裡至少還有一格」。lo 等於 hi 時還剩一格，要再看一次；lo 跑到 hi 右邊，範圍空了，目標不存在。注意 mid + 1、mid - 1 的那個 1 不能省：寫成 lo = mid 的話，剩兩格時 mid 會一直等於 lo，範圍永遠不會縮小，程式就停不下來（第 8 課的無窮迴圈）。

二分搜尋快的原因在於「每比一次就排除一半」：8 格最多比 4 次，16 格最多 5 次，每多一倍資料只多比 1 次。但它完全依賴「排好序」這個前提，因為「中間這格比目標小，左邊全部更小」這個推論只在排好的資料上成立。資料沒排好時，程式不會報錯，只會安靜地給出錯誤答案：

5. 資料變大時，差距越來越大

把兩種搜尋在最壞情況要比幾次列出來（都用本頁的程式實際跑過）：資料多 10 倍，線性搜尋的工作量也多 10 倍；二分搜尋每次把範圍砍半，資料多一倍才多比 1 次，100 萬筆也只要 20 次。資料小的時候兩者差不多，資料越大，差距就越驚人。

不過二分搜尋的前提要付代價：資料得先排好，而排序本身比線性搜尋整排看一遍還費工。所以只找一次的話，直接線性搜尋反而划算；同一份資料要反覆查很多次（例如整天都有顧客來問書），先排好一次、之後都用二分搜尋，才會省下大量時間。挑演算法永遠要看「資料多大、查幾次、資料會不會常常變」。

6. 四種做法比一比

7. 實務上：直接用內建的

自己寫搜尋和排序是為了理解電腦在做什麼；真正寫程式時，請直接用 Python 內建的工具，它們經過大量測試，也快得多。sorted(串列) 回傳一個排好的新串列，原本的不變；串列.sort() 就地排好原本的串列，回傳 None（第 5 課的重點）。兩者都可以加 reverse=True 改成由大到小。Python 官方的排序指南提到，內建排序使用的 Timsort 演算法會利用資料裡原本就已經排好的片段，所以資料越接近排好，排得越快。

搜尋方面，in 和 index() 在串列上是線性搜尋；如果同一批資料要反覆查「有沒有」，第 6 課的字典和第 11 課的集合用的是另一種查法，不必一格一格比，查詢通常比串列快很多。真的需要在排好的串列上做二分搜尋時，標準函式庫有現成的 bisect 模組（要用 import 載入，本系列先不展開）。只是要最大值或最小值，用 max()、min() 就好，不必為此整個排序。

# 北辰書店的書號與書名（示意）
codes = [305, 112, 478, 220, 156]
titles = ["資料結構", "Python 入門", "演算法圖解", "AI 導論"]

print(220 in codes)              # in：一格一格找（線性搜尋），回答有或沒有
if 999 in codes:                 # 先確認有沒有，再問位置
    print(codes.index(999))
else:
    print("沒有 999 這本")
print(codes.index(220))          # index()：第一個 220 在索引幾號

ranked = sorted(codes)           # 回傳「新的」排好的串列，codes 不變
print(ranked, codes)
codes.sort(reverse=True)         # 就地由大到小排，回傳 None
print(codes)
print(sorted(titles))            # 字串依字元編碼排序，不是筆畫或注音
print(min(codes), max(codes))    # 只要最小、最大值，不必整個排序
# 輸出：
# True
# 沒有 999 這本
# 3
# [112, 156, 220, 305, 478] [305, 112, 478, 220, 156]
# [478, 305, 220, 156, 112]
# ['AI 導論', 'Python 入門', '演算法圖解', '資料結構']
# 112 478

注意字串排序的結果：英文字母排在中文前面，中文的順序也不是依筆畫或注音，而是依每個字在電腦裡的編碼大小。要照別的規則排（例如依書名長度），可以傳 key 參數，例如 sorted(titles, key=len)，官方排序指南有更多例子。

8. 把兩種搜尋寫成函式

實驗室四背後用的，就是下面這兩個函式（JavaScript 版本一行對一行照抄，結果和 Python 實際執行相同）。它們用第 9 課的 return 回傳結果，而且一次回傳兩個值：第 11 課說過，這其實是回傳一個元組 (索引, 比較次數)。

def linear_search(items, target):
    count = 0
    for i in range(len(items)):
        count = count + 1
        if items[i] == target:
            return i, count            # 找到：回傳（索引, 比較次數）
    return -1, count                   # 全部看完都沒有

def binary_search(items, target):      # items 必須已經由小到大排好
    lo = 0
    hi = len(items) - 1
    count = 0
    while lo <= hi:
        mid = (lo + hi) // 2           # 範圍正中間的索引
        count = count + 1
        if items[mid] == target:
            return mid, count
        elif items[mid] < target:
            lo = mid + 1               # 丟掉左半邊
        else:
            hi = mid - 1               # 丟掉右半邊
    return -1, count

codes = [8, 17, 23, 35, 42, 56, 61, 79]
print(linear_search(codes, 61))        # 從頭找
print(binary_search(codes, 61))        # 每次砍一半
print(binary_search(codes, 30))        # 找不到
big = list(range(0, 2000000, 2))       # 100 萬個由小到大的偶數（示意）
print(linear_search(big, 1999998))
print(binary_search(big, 1999998))
# 輸出：
# (6, 7)
# (6, 3)
# (-1, 3)
# (999999, 1000000)
# (999999, 20)

函式裡用的是 return 而不是 break：找到時直接把結果交回去，函式立刻結束，迴圈自然也不會再跑。最後兩行用 100 萬筆資料找最後一個數，線性搜尋實際比了 1,000,000 次，二分搜尋只比了 20 次。

9. 常見錯誤與錯誤訊息的長相

搜尋與排序最常見的錯，一半會出現錯誤訊息，一半不會。以下是 Python 3.13 實際執行的畫面（File 後面原本是完整路徑，這裡簡寫成 main.py）：

① 用 index() 找不存在的值Traceback (most recent call last):
  File "main.py", line 2, in <module>
    print(codes.index(220))
          ~~~~~~~~~~~^^^^^
ValueError: 220 is not in list

② 二分搜尋把 hi 設成 len(codes)，少了 - 1（目標比最大的還大時才會發生）Traceback (most recent call last):
  File "main.py", line 7, in <module>
    if codes[mid] == target:
       ~~~~~^^^^^
IndexError: list index out of range

③ 把 sort() 的回傳值當成串列（它回傳的是 None）Traceback (most recent call last):
  File "main.py", line 2, in <module>
    smallest = codes.sort()[0]
               ~~~~~~~~~~~~^^^
TypeError: 'NoneType' object is not subscriptable

④ 串列裡混了數字和字串，無法比較大小Traceback (most recent call last):
  File "main.py", line 2, in <module>
    print(sorted(codes))
          ~~~~~~^^^^^^^
TypeError: '<' not supported between instances of 'str' and 'int'

第 ④ 個常發生在資料是從檔案或 input() 讀進來的時候：第 3 課說過 input() 永遠回傳字串，"8" 和 17 不能比大小，要先用 int() 轉換。另外，氣泡排序的內層如果寫成 range(n)，最後一圈的 codes[j + 1] 會超出範圍，同樣是 IndexError（自我檢測第 6 題）。

不會出現錯誤訊息的錯更難抓，最常見的有三種：在沒排序的資料上用二分搜尋，安靜地回傳錯誤答案（第 4 節的圖）；氣泡排序的內層少寫 - i，結果還是對的，只是每一輪都多比了已經排好的格子；二分搜尋寫成 lo = mid，範圍縮不下去，程式停不下來。遇到「答案怪怪的」或「一直跑不完」，就用本頁播放器的方式，一步一步追 ▲lo、▲mid、▲hi 的位置，或在迴圈裡 print 出這三個值（第 10 課的除錯方法）。

10. 以後會在哪裡遇到

讀 AI 或資料分析的範例程式時，排序與搜尋幾乎無所不在，只是換了名字：pandas 的 sort_values()、nlargest() 是排序後取前幾名；資料庫幫欄位建索引（index），就是先排好再用類似二分搜尋的方法快速查詢；推薦系統、RAG 的向量資料庫要在上百萬筆資料裡找「最相近的幾筆」，K 近鄰（KNN）模型也是在找距離最近的鄰居，這些工具花了很大的工夫，就是為了不要一筆一筆比完。下一課的遞迴（recursion），則是另一種描述「把問題切成一半再處理」的寫法，二分搜尋也可以用遞迴寫。

✅ 自我檢測

6 題原創的程式閱讀題，每一題的答案都用 Python 3.13 實際執行確認過。選完立即顯示對錯與解析，全部作答後會出現總分。目前得分：0 / 6