F. 搜尋：線性與二分
搜尋就是「在一堆資料裡找出目標在哪一格」。考卷上最常見的就兩種寫法：老實一格一格找的線性搜尋，和每次砍掉一半的二分搜尋。
¶線性搜尋：從頭找到尾
#include <iostream>
using namespace std;
int a[8] = {3, 7, 12, 18, 25, 31, 40, 56};
// 從頭找到尾；找到就回傳位置，找不到回傳 -1
int linearSearch(int n, int target) {
for (int i = 0; i < n; i++) {
if (a[i] == target) return i; // 找到就直接結束，後面不用再看
}
return -1;
}
int main() {
cout << linearSearch(8, 40) << '\n';
cout << linearSearch(8, 20) << '\n';
return 0;
}
執行結果：
6
-1沒有玄機：從 a[0] 一格一格比下去，一樣就 return 位置、函式當場結束。找不到時回傳 -1——陣列沒有第 -1 格，拿它當「查無此人」的暗號是通用慣例。
代價是最壞情況要看完全部 n 格：目標在最後一格，或根本不在裡面。資料一多，這就是 4.9 那種 TLE 的來源。
¶二分搜尋：前提是資料已經排好
三個變數（名字各家不同，l／r／m、low／high／mid 都是同一件事）：
| 變數 | 意思 |
|---|---|
le |
還沒被排除的範圍，最左邊的索引 |
ri |
還沒被排除的範圍，最右邊的索引 |
mid |
這一輪要檢查的正中間那格，(le + ri) / 2（整數除法自動捨去小數，2.6） |
#include <iostream>
using namespace std;
int a[8] = {3, 7, 12, 18, 25, 31, 40, 56}; // 前提：已經由小到大排好
int binarySearch(int n, int target) {
int le = 0, ri = n - 1; // 還沒排除的範圍是 a[le] ~ a[ri]
while (le <= ri) {
int mid = (le + ri) / 2; // 看範圍正中間那一格
if (a[mid] == target) return mid;
if (a[mid] < target) le = mid + 1; // 目標比中間大：左半邊整個不用看
else ri = mid - 1; // 目標比中間小：右半邊整個不用看
}
return -1; // 範圍空了還沒找到
}
int main() {
cout << binarySearch(8, 40) << '\n';
cout << binarySearch(8, 20) << '\n';
return 0;
}
執行結果：
6
-1¶追蹤一次：在 8 格裡找 40
| 輪 | le |
ri |
mid |
a[mid] |
判斷 | 接下來 |
|---|---|---|---|---|---|---|
| 1 | 0 | 7 | 3 | 18 | 18 < 40 | le = mid + 1 = 4 |
| 2 | 4 | 7 | 5 | 31 | 31 < 40 | le = mid + 1 = 6 |
| 3 | 6 | 7 | 6 | 40 | 相等 | 回傳 6 |
三輪就到手。找不到也是同一套：找 20 時三輪之後變成 le = 4、ri = 3，le <= ri 不成立，迴圈結束回傳 -1。
範圍每輪至少砍掉一半，所以 n 格最多只要 \log_2 n 輪出頭——n = 8 最多 4 輪，n = 10^6 最多 20 輪，而線性搜尋在同樣的一百萬筆最壞要看一百萬次。這就是 17.6 講的 \log 複雜度。
¶遞迴版：同一件事的另一種寫法
同一件事也可以用遞迴寫（D 節），考卷兩種都可能出現：
#include <iostream>
using namespace std;
int a[8] = {3, 7, 12, 18, 25, 31, 40, 56};
int binarySearch(int le, int ri, int target) {
if (le > ri) return -1; // 範圍空了：找不到
int mid = (le + ri) / 2;
if (a[mid] == target) return mid;
if (a[mid] < target) return binarySearch(mid + 1, ri, target);
return binarySearch(le, mid - 1, target);
}
int main() {
cout << binarySearch(0, 7, 40) << '\n';
cout << binarySearch(0, 7, 20) << '\n';
return 0;
}
執行結果：
6
-1兩版邏輯完全相同，差別只在怎麼進到下一輪：while 版把新的 le、ri 存回變數再繞回迴圈開頭，遞迴版把新的 le、ri 當參數呼叫自己，範圍空掉的判斷從迴圈條件搬到開頭那行 if。讀考卷時認得出「算 mid、比一次、只往一邊走」這個骨架就夠了。