Learning Objectives
- 說明線性搜尋的做法，以及最壞情況要比較 n 次
- 說明二分搜尋的前提是資料已經排序，並追蹤每一輪如何排除一半
- 追蹤選擇排序的每一輪，說明它為什麼是 O(n²)
- 說出插入排序、氣泡排序、合併排序、快速排序的基本想法與複雜度
- 判斷什麼情況值得先排序再搜尋
每天都在用的兩件事：找東西與排順序
在購物網站按「價格由低到高」，是排序（sorting）；在通訊錄輸入名字找人，是搜尋（searching）。 這兩件事是電腦最常做的工作之一：資料庫、搜尋引擎、試算表、手機相簿，背後都有排序與搜尋的演算法。
這一課要回答的問題是：資料有沒有排好，對搜尋的速度影響有多大？排序本身又要花多少步？
我們會用第 24 課的 Big-O 來比較，並用第 25 課的陣列當作資料的存放方式。
線性搜尋：從頭一個一個比
最直接的做法是從第一個開始，一個一個和目標比較，相等就回報位置；全部比完都不相等，就回報找不到（慣例是回傳 -1）。 這叫線性搜尋（linear search）。
它的好處是不挑資料：沒排序也可以用。缺點是最壞情況（目標在最後一個，或根本不在裡面）要比較 n 次，是 O(n)。
線性搜尋：一格一格往右
在 6 個學號裡找 63 和 50。看上方的 ▲ 一格一格往右移：找 63 時比到第 5 個才找到；找 50 時 6 個全部比完，才能確定它不在裡面。
二分搜尋：每次排除一半
翻字典找一個詞，你不會從第一頁開始翻，而是翻到中間，看那一頁的字在目標前面還是後面，再決定往哪一半找。 這就是二分搜尋（binary search）。它有一個前提：資料必須已經由小到大排好。
做法是用 lo、hi 兩個索引圍出「目標如果存在，一定在這個範圍裡」：
- 一開始範圍是整個陣列：
lo = 0、hi = n - 1 - 看範圍正中間的
mid = (lo + hi) // 2 a[mid]等於目標：找到了a[mid]比目標小：目標只可能在右半邊，lo = mid + 1a[mid]比目標大：目標只可能在左半邊，hi = mid - 1- 只要
lo <= hi範圍裡就還有元素，回到第 2 步；lo > hi表示範圍空了，目標不在裡面
每比一次就排除一半，和第 24 課的猜數字一樣，最多只要比較約 log₂n 次，是 O(log n)。
二分搜尋：看 lo、mid、hi 怎麼移動
灰掉的格子已經不在搜尋範圍裡。找 66 時，第一輪看中間的 34，比 66 小，左半邊整段被排除，第二輪就找到了。找 20 時，範圍一路縮小，最後 lo 跑到 hi 的右邊（範圍空了），回傳 -1。10 個元素最多只要比 4 次。
兩種搜尋差多少
最壞情況下的比較次數：
| 資料筆數 n | 線性搜尋 | 二分搜尋 |
|---|---|---|
| 10 | 10 | 4 |
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
| 1,000,000,000 | 1,000,000,000 | 30 |
資料越多，差距越大。這也是為什麼字典、電話簿、資料庫的索引都要「排好順序」：排一次，之後的每一次搜尋都能用二分搜尋。
想一想：搜尋
二分搜尋能正確運作，資料一定要符合哪個條件？
一份已經排序的名單有 1,000,000 筆資料，用二分搜尋找一個人，最多要比較幾次？
下面的程式會印出什麼？
a = [7, 3, 9, 3, 5]
count = 0
for x in a:
count += 1
if x == 3:
break
print(count)
選擇排序：每一輪挑出最小的
排序最容易理解的方法之一是選擇排序（selection sort），就像整理一手撲克牌時，每次從還沒整理的牌裡挑出最小的，放到最左邊：
- 第 1 輪：在全部 n 個數裡找出最小的，和第 0 格交換
- 第 2 輪：在剩下的 n - 1 個數裡找出最小的，和第 1 格交換
- 依此類推，做 n - 1 輪，全部就排好了
每一輪都要把剩下的數全部看過，比較次數是 (n - 1) + (n - 2) + … + 1 = n × (n - 1) ÷ 2，和第 24 課的握手次數一樣，是 O(n²)。
選擇排序：一輪一輪看
長條的高度就是數值。▲ i 是這一輪要放的位置，▲ j 往右掃描，「目前最小」記住掃描到現在最小的那一格。每一輪結束時交換一次，左邊排好的部分就多一格。
其他常見的排序方法
排序的方法很多，下面是最常聽到的幾種：
| 方法 | 想法 | 複雜度 |
|---|---|---|
| 選擇排序 | 每輪挑出剩下最小的，放到前面 | O(n²)，不管資料長怎樣都要比完 |
| 插入排序 | 像整理手上的牌：拿起下一張，往左插到正確位置 | 最壞 O(n²)；資料幾乎排好時很快，接近 O(n) |
| 氣泡排序 | 相鄰兩個比較，順序錯就交換，大的會像氣泡一樣浮到最後 | 最壞 O(n²) |
| 合併排序 | 把資料切成兩半，各自排好，再把兩個排好的部分合併 | O(n log n) |
| 快速排序 | 挑一個基準值，比它小的放左邊、大的放右邊，兩邊再各自排 | 平均 O(n log n)；基準選得很差時是 O(n²) |
合併排序和快速排序都用了分而治之（divide and conquer）的想法：把大問題切成小問題，小問題解完再組合起來。 合併排序一般認為最早由馮紐曼（von Neumann）在 1945 年寫出，他也是第 10 課「馮紐曼架構」的那位馮紐曼。
O(n²) 和 O(n log n) 在資料多時差很多：排序一百萬筆資料，n² 是 10¹² 步，n log₂n 大約只有 2 × 10⁷ 步。
實際寫程式時，直接用語言內建的排序就好（例如 Python 的 sorted() 和 list.sort()），它們都是 O(n log n) 而且經過高度最佳化。
下面的小工具讓幾種排序在同一份資料上賽跑，每一步是一次比較或一次交換（移動、寫入）。
從賽跑看到的事
- 資料已經排好時，插入排序和氣泡排序很快就發現「不用動」，選擇排序卻還是要把 n × (n - 1) ÷ 2 次比較全部做完
- 選擇排序每一輪最多只交換一次，所以交換次數最少；如果「搬動資料」很花時間，這是它的優點
- 資料只有 10 筆時，合併排序的比較次數不一定最少；調到 30 筆以上，O(n log n) 的合併排序就明顯比三種 O(n²) 的排序少，筆數越多差距越大
- 沒有一種排序在每種情況都最好，這也是為什麼要分析演算法：看資料的特性與最在意的成本來選
想一想：排序
用選擇排序排 5 個數，下面的程式會印出什麼？
a = [5, 1, 4, 2, 3]
n = len(a)
comparisons = 0
for i in range(n - 1):
smallest = i
for j in range(i + 1, n):
comparisons += 1
if a[j] < a[smallest]:
smallest = j
a[i], a[smallest] = a[smallest], a[i]
print(comparisons)
排序 1,000,000 筆資料，O(n²) 的方法大約要 10¹² 步。O(n log n) 的方法大約要幾步？
一份沒有排序的名單，你只需要找一次某個人。先排序再用二分搜尋，還是直接線性搜尋比較划算？
實作：完成二分搜尋
圖書館的書依編號排好放在 books 裡。binary_search 已經會算 mid、也會在找到時回傳，請完成 TODO：a[mid] 比目標小時要往右半邊找，比目標大時要往左半邊找。完成後記得刪掉 break 那一行，再按「執行並檢查」。
重點整理
- 線性搜尋從頭一個一個比，不需要排序，最壞 n 次，O(n)
- 二分搜尋要求資料已經排序，每次看中間、排除一半，最多約 log₂n 次，O(log n)
- 選擇排序每輪挑出剩下最小的，比較次數 n × (n - 1) ÷ 2，O(n²)；插入排序、氣泡排序最壞也是 O(n²)
- 合併排序、快速排序用分而治之，O(n log n)（快速排序是平均情況）；實際寫程式用語言內建的排序
- 只找一次就直接線性搜尋；要找很多次，先排序一次再用二分搜尋比較划算
下一課：資料庫。資料庫為了讓查詢變快，也會先替資料建立排好順序的「索引」，用的正是這一課的想法。 想看更多排序方法的細節與程式，可以接著上演算法軌（第 04、06～09 課）。