基礎程式設計（Java）· CH19
用對演算法、看懂效率 · 導覽地圖
完整內容看 PDF 講義，二分搜尋砍半動畫與試跑看 index。
兩件基本事
同一件事常有好幾種演算法，差別不在「做不做得到」，而在「資料變多時要花多少工」——這就是 Big O 在量的事。
搜尋型一
for (int i = 0; i < data.length; i++)
if (data[i] == key) return i; // 找到回索引
return -1; // 沒找到回哨兵值不必排序，任何陣列都能用。最壞情況（在最後或不存在）比對 n 次 → O(n)。
搜尋型二
找 23：中間 12<23 → 砍掉左半往右找。前提：已排序。每輪砍半 → O(log n)，1000 筆最多約 10 次。
二分搜尋的程式
int low = 0, high = a.length - 1;
while (low <= high) { // 相等時還剩一格要查
int mid = (low + high) / 2;
if (key == a[mid]) return mid;
else if (key < a[mid]) high = mid - 1; // 砍右半
else low = mid + 1; // 砍左半
}條件 low <= high、邊界 ±1（少了會無窮迴圈）。
效率語言
| Big O | 名稱 | 例子 |
|---|---|---|
O(1) | 常數 | 取 a[i]、比大小 |
O(log n) | 對數 | 二分搜尋 |
O(n) | 線性 | 線性搜尋 |
O(n log n) | 線性對數 | 合併排序 |
O(n²) | 平方 | 選擇／插入排序 |
化簡：丟常數倍與低次項，只留最高次項（O(2n²+3n+100) → O(n²)）。
排序型一
for (int i = 0; i < a.length - 1; i++) {
int m = i; // 初值是 i，不是 0
for (int j = i+1; j < a.length; j++)
if (a[j] < a[m]) m = j; // 找剩餘最小
int t = a[i]; a[i] = a[m]; a[m] = t; // 換到前面就位
}外迴圈 n、內迴圈 ~n → 巢狀 → O(n²)。不因資料排得多齊而變快。
排序型二
for (int i = 1; i < a.length; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; }
a[j+1] = key; // key 放進空出的位置
}像整理手上的撲克牌。最壞 O(n²)；若資料「近乎排好」會很快（接近 O(n)）。
排序型三
mergeSort(a, low, mid); // 排左半
mergeSort(a, mid+1, high); // 排右半
merge(a, low, mid, high); // 合併兩段已排序拆 log n 層、每層合併共掃 n 格 → O(n log n)，遠快於 O(n²)；代價是需額外暫存空間。
選型
實務上直接用 java.util.Arrays.sort／Arrays.binarySearch（須先排序）。
接下來