排序與搜尋
二分搜尋
二分搜尋在有序清單中找值的辦法，是不斷把可能的範圍對半砍掉。看中間那個元素：若它正是目標，就找到了；若目標更小，就丟掉整個上半部分；若更大，就丟掉下半部分。每看一次，剩下的就少一半。這正是你在辭典裡查單字的方式——你不會從第 1 頁讀起，而是翻到中間，再決定往哪邊走。
其機制是一個由兩個索引 low 和 high 框定、不斷收縮的窗口，中間取 mid = (low + high) / 2。每次比較讓 low 上移或 high 下移，窗口便持續合攏；當找到目標、或窗口為空（low > high）時搜尋結束。唯一不可商量的前提是：資料必須按你比較的鍵有序——在無序資料上，「丟掉一半」的推理就站不住腳了。
反覆對半正是它飛快的原因：從 n 個元素出發，約 log2(n) 步就能收斂到唯一候選——時間 O(log n)，額外空間 O(1)。一百萬個元素也只需約二十次比較。代價是你必須保持資料有序（且放在支援快速隨機存取的結構裡，比如陣列）；若只是在無序資料裡做一次性搜尋，樸素的線性搜尋也許更省事。
int binarySearch(const std::vector<int>& a, int target) {
int low = 0, high = (int)a.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (a[mid] == target) return mid;
else if (a[mid] < target) low = mid + 1; // go right
else high = mid - 1; // go left
}
return -1; // not found
}每一步都把搜尋範圍對半減少，所以 n 個元素的有序陣列只需約 log2(n) 次比較。
用 mid = low + (high - low) / 2 而不是 (low + high) / 2；在超大陣列上，後者會因 low + high 超出整數上限而溢位。這是許多教科書實作裡有名的 bug。
又稱
另見