二分搜尋 Binary search · 演算法 Algorithms

二分搜尋

在排好序的資料裡，每看一格就丟掉一半：一百萬筆最多只要看二十格。

資料筆數

要找

1/6

mid：正在看的中間格找到已排除（lo–hi 範圍外）

二分搜尋：已看

二分搜尋：這次總共

31 筆最多要看

線性搜尋要看

要在 31 個排好序的數字裡找 56。因為已經排好序，可以從中間開始看。

亮起來的是這一步執行的程式碼

1function binarySearch(a: number[], target: number): number {
2  let lo = 0, hi = a.length - 1;
3  while (lo <= hi) {
4    const mid = lo + ((hi - lo) >> 1);
5    const value = a[mid];
6    if (value === target) return mid;
7    if (value < target) lo = mid + 1;
8    else hi = mid - 1;
9  }
10  return -1;
11}
12 
13function linearSearch(a: number[], target: number): number {
14  for (let i = 0; i < a.length; i++) {
15    if (a[i] === target) return i;
16  }
17  return -1;
18}

模型假設與範圍

Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。

什麼時候用

資料已經排序，而且能直接跳到任何一個位置（陣列、固定長度的紀錄）。
不只找值：也能找「第一個 ≥ x 的位置」，拿來做範圍查詢或決定插入點。
答案有單調性的問題也能二分：例如「最小的可行容量」——猜一個值、檢查可不可行、丟掉一半。

和其他主題的關係

由這些組成: 資料結構 · 動態陣列
被這些用到: 考題：最長遞增子序列考題：資料流的中位數系統設計 · 一致性雜湊
延伸閱讀: 資料結構 · 二元搜尋樹排序

語言內建的版本

JavaScript 沒有內建的二分搜尋。indexOf、findIndex 都是從頭一個一個找，O(n)。下面是常用的 lower bound：回傳第一個 ≥ x 的位置。

操作	寫法	成本
第一個 ≥ x 的位置	`lowerBound(a, 3)`	O(log n)
線性找第一個符合的	`a.findIndex((v) => v >= 3)`	O(n)
線性找最後一個符合的	`a.findLastIndex((v) => v <= 3)`	O(n)

function lowerBound(a: number[], x: number): number {
  let lo = 0, hi = a.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] < x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}
 
const a = [1, 3, 3, 3, 7];
lowerBound(a, 3);                   // → 1
lowerBound(a, 4);                   // → 4
lowerBound(a, 8);                   // → 5
lowerBound(a, 4) - lowerBound(a, 3);  // → 3
a.findIndex((v) => v >= 3);         // → 1
a.findLastIndex((v) => v <= 3);     // → 3
a.indexOf(5);                       // → -1

每個 → 後面的結果都是實際執行這段程式碼驗證過的。

寫成「左閉右開」[lo, hi)、迴圈條件 lo < hi、結束時 lo 就是答案，邊界最不容易錯。upper bound（第一個 > x）只要把 < 改成 <=。
用 lo + Math.floor((hi - lo) / 2) 取中點。JavaScript 位元運算會先轉成 32 位整數；即使 lo、hi 各自小於 2^32，兩者相加後仍可能被 >>> 截斷，讓搜尋無法收斂。
findLastIndex 是 ES2023 才有的（Node 18 起）。

時間與空間複雜度（Big O）

操作	平均	最差
二分搜尋資料必須已經排序	O(log n)	O(log n)
線性搜尋	O(n)	O(n)
先排序再二分搜尋一次只查一次的話，比線性搜尋還慢	O(n log n)	O(n log n)

空間：O(1)，只需要 lo、hi、mid 三個變數

Big O 實測：n 變大時步數怎麼長

數的是：看了幾格（線性搜尋是 64 個隨機目標的平均）

	Big O	n = 1,000	n = 10,000	n = 100,000	n = 1,000,000	成長倍數：實測（理論）
二分搜尋（最差）	O(log n)	10	14	17	20	×2.0 (×2.0)
二分搜尋（平均）	O(log n)	9.5	12.9	16.2	19.4	×2.1 (×2.0)
線性搜尋（平均）	O(n)	380	3,796	37,960	379,591	×999 (×1,000)

n 變成 1,000 倍，二分搜尋最差只多看了 10 格；線性搜尋要看的格數也跟著變成約 1,000 倍。

和其他做法比

	二分搜尋：最多看幾格（實測）	二分搜尋：平均	線性搜尋：最多
15 筆	4	3.6	15
1,000 筆	10	9.5	1,000
1,000,000 筆	20	19.4	1,000,000
1,000,000,000 筆	30	29.4	1,000,000,000

二分搜尋的數字是真的去搜出來的：小資料把每個存在的值和每個空隙都搜一次，大資料搜兩端、兩端之外，再加兩萬個固定種子的隨機目標（資料不必真的存在，用「第 i 格的值是 2i」的函式代替）。線性搜尋最壞要看完全部，所以就是 n。

真實世界裡的它

git bisect 用二分搜尋找出是哪一個 commit 引入了 bug。
資料庫的 B-tree 索引在每個節點裡用二分搜尋找該往哪個子節點走。
一致性雜湊在排好序的環上用二分搜尋找下一台伺服器。

取捨與陷阱

資料沒排序就不能用。為了一次搜尋先排序（n log n）比直接掃一遍（n）還貴，排序的成本要分攤到很多次查詢才划算。
經典 bug：mid = (lo + hi) / 2 在固定寬度整數下會溢位，要寫成 lo + (hi − lo) / 2。
邊界條件（lo ≤ hi 還是 lo < hi、hi = mid 還是 mid − 1）最容易寫錯，錯了會無窮迴圈或漏掉最後一格。
在鏈結串列上沒有用：光是走到中間就要 n/2 步。

演算法