二分搜尋是「看起來最簡單、最容易寫錯」的演算法。while 條件用 < 還是 <=？hi 要設 mid 還是 mid-1？答錯一個就無限迴圈或漏掉答案。
這篇要打掉一個迷思：二分搜尋的前提不是「陣列已排序」，而是「答案空間單調」——只要你能定義一個「是/否」判斷，而且它隨著搜尋變數單調變化，就能二分。延續一貫的完整推導流程：
📋 題目 → 🧭 拆解 → 暴力 → 瓶頸 → 洞察 → 最優 → 程式碼
- 標準模板（704）→ 旋轉陣列搜尋（33）→ 找最小值/轉折點（153）→ 對答案二分（875）→ 兩陣列中位數分割（4）
① LC 704 — Binary Search
📋 題目：給定升序排列、無重複的整數陣列 nums 與目標 target，回傳 target 的索引；不存在則回傳 -1。要求 O(log n)。
範例：nums = [-1,0,3,5,9,12], target = 9 → 4；target = 2 → -1
🌐 EN — Given an ascending, duplicate-free integer array
numsand atarget, return its index, or-1if absent. O(log n) required. Example:nums = [-1,0,3,5,9,12],target = 9→4;target = 2→-1
🧭 從讀題到解法
- 拆解：已排序、要 O(log n)——這是二分搜尋的「教科書原型」。
- 暴力解：線性掃一遍 O(n)，但浪費了「已排序」這個條件。
- 關鍵洞察：每次看中點，就能把搜尋範圍砍一半——
nums[mid]比 target 小，答案在右半；大則在左半。 - 最優解：維持閉區間
[lo, hi]，lo <= hi時持續收斂。先把模板背到肌肉記憶，後面四題都是它的變形。
def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi: # closed interval [lo, hi]
mid = lo + (hi - lo) // 2 # avoid overflow
if nums[mid] == target:
return mid
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
int search(vector<int>& nums, int target) {
int lo = 0, hi = nums.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // avoid overflow
if (nums[mid] == target) return mid;
else if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
- 複雜度：時間 O(log n)，空間 O(1)。
- 坑：①
mid = lo + (hi-lo)/2而非(lo+hi)/2，避免大數溢位；② 閉區間配lo <= hi、hi = mid - 1——三者要一致，混用就會出錯。
② LC 33 — Search in Rotated Sorted Array
📋 題目：升序陣列在某未知點被「旋轉」（如 [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]），無重複。在其中找 target 的索引，要求 O(log n)。
範例：nums = [4,5,6,7,0,1,2], target = 0 → 4；target = 3 → -1
🌐 EN — An ascending array is rotated at some unknown pivot (e.g.
[0,1,2,4,5,6,7]→[4,5,6,7,0,1,2]), no duplicates. Findtarget's index in O(log n). Example:nums = [4,5,6,7,0,1,2],target = 0→4;target = 3→-1
🧭 從讀題到解法
- 拆解：整體不再升序，但它是「兩段各自升序」拼起來的。
- 想先找轉折點再二分？可以，但要掃兩次。有沒有辦法一次二分直接搞定？
- 關鍵洞察：取中點後，
[lo, mid]與[mid, hi]至少有一半是完全升序的。判斷哪一半有序，再看 target 是否落在「那個有序半段的範圍內」，就知道往哪邊收。 - 最優解：用
nums[lo] <= nums[mid]判斷左半是否有序，分兩種情況各自決定丟哪半。
def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # left half is sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
int search(vector<int>& nums, int target) {
int lo = 0, hi = nums.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
if (nums[lo] <= nums[mid]) { // left half is sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // right half is sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
- 複雜度：時間 O(log n)，空間 O(1)。
- 坑：判斷有序半段要用
nums[lo] <= nums[mid]（含等號），因為lo == mid時也算左半有序。比較範圍時務必用「有序那一半的兩端」夾 target，別憑感覺。
③ LC 153 — Find Minimum in Rotated Sorted Array
📋 題目：同樣是旋轉後的升序、無重複陣列，找出最小值，要求 O(log n)。
範例：nums = [3,4,5,1,2] → 1；nums = [4,5,6,7,0,1,2] → 0
🌐 EN — A length-
nascending array (unique elements) is rotated 1 to n times. Given the rotated arraynums, return its minimum element, in O(log n). Example:nums = [3,4,5,1,2]→1;nums = [4,5,6,7,0,1,2]→0
🧭 從讀題到解法
- 拆解：最小值就是「轉折點」——那個比前一個元素小的位置。
- 暴力解：掃一遍找最小，O(n)，但沒用上結構。
- 關鍵洞察：拿
nums[mid]跟右端nums[hi]比。若nums[mid] > nums[hi]，代表轉折點在 mid 右邊（右半「掉下去」了），最小值在(mid, hi]；否則最小值在[lo, mid]（含 mid）。 - 最優解：這題沒有明確的 target，是「找邊界」型二分，用
lo < hi+hi = mid（不是mid-1，因為 mid 本身可能就是答案）。
def findMin(nums):
lo, hi = 0, len(nums) - 1
while lo < hi: # converge to a single index
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]: # min is strictly to the right of mid
lo = mid + 1
else: # min is at mid or to its left
hi = mid
return nums[lo]
int findMin(vector<int>& nums) {
int lo = 0, hi = nums.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[hi]) lo = mid + 1; // min is to the right
else hi = mid; // min is at mid or left
}
return nums[lo];
}
- 複雜度：時間 O(log n)，空間 O(1)。
- 坑：① 要跟
nums[hi]比，不能跟nums[lo]比——跟左端比在沒旋轉的情況會誤判；② 用lo < hi（不是<=）配hi = mid，否則無限迴圈。這是「找邊界」二分的標準寫法，和 704 的「找精確值」寫法不同。
④ LC 875 — Koko Eating Bananas
📋 題目：有 piles 堆香蕉，Koko 每小時挑一堆、以速度 k（根/小時）吃；一小時內吃不完一堆也不會換堆。給定時限 h 小時，求能在 h 小時內吃完的最小整數速度 k。
範例：piles = [3,6,7,11], h = 8 → 4；piles = [30,11,23,4,20], h = 5 → 30
🌐 EN — There are
pilesof bananas; each hour Koko picks one pile and eats at speedkbananas/hour (if a pile has fewer thankleft, she finishes it and waits out the hour). Given a deadline ofhhours, find the minimum integer speed k to finish all bananas withinhhours. Example:piles = [3,6,7,11],h = 8→4;piles = [30,11,23,4,20],h = 5→30
🧭 從讀題到解法
- 拆解：要找「最小的可行 k」。陣列本身根本不用排序——這題的二分不是搜陣列。
- 暴力解：從 k=1 開始一路試到能在 h 小時內吃完，O(max(piles) · n)，太慢。
- 關鍵洞察（對答案二分）：定義判斷式
canFinish(k)= 「速度 k 能否在 h 小時內吃完」。速度越快、花的時間越少——所以canFinish(k)對 k 是單調的（false…false、true…true）。我們要找「false→true 的第一個 true」。只要判斷式單調，搜尋空間就能二分，哪怕沒有任何排序好的陣列。 - 最優解：在答案區間
[1, max(piles)]上二分，每次用ceil(pile/k)累加總時數判斷可行性。
def minEatingSpeed(piles, h):
def hours(k): # hours needed at speed k
return sum((p + k - 1) // k for p in piles) # ceil division
lo, hi = 1, max(piles)
while lo < hi:
mid = lo + (hi - lo) // 2
if hours(mid) <= h: # feasible → try a slower speed
hi = mid
else: # too slow → must speed up
lo = mid + 1
return lo
int minEatingSpeed(vector<int>& piles, int h) {
auto hours = [&](int k) {
long long t = 0;
for (int p : piles) t += (p + k - 1) / k; // ceil division
return t;
};
int lo = 1, hi = *max_element(piles.begin(), piles.end());
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (hours(mid) <= h) hi = mid; // feasible → slower
else lo = mid + 1; // too slow → faster
}
return lo;
}
- 複雜度：時間 O(n · log(max(piles)))，空間 O(1)。
- 坑：① 二分的是答案空間（速度），不是輸入陣列；②
ceil(p/k)寫成(p + k - 1) // k；③ 速度下限是 1（不是 0，會除零）；④ 想清楚單調方向：可行就往「更小 k」收（hi = mid）。
💡 辨識訊號：題目出現「最小的能…/最大的不超過…」且存在一個單調可行性判斷，幾乎都是「對答案二分」。同類題：分割陣列最大值最小（410）、運送包裹（1011）。
⑤ LC 4 — Median of Two Sorted Arrays
📋 題目：給兩個各自升序的陣列 A、B，回傳兩者合併後的中位數，要求時間 O(log(m+n))。
範例：A = [1,3], B = [2] → 2.0；A = [1,2], B = [3,4] → 2.5
🌐 EN — Given two ascending arrays
A,Bof sizesmandn, return the median of their merge, in O(log(m+n)). Example:A = [1,3],B = [2]→2.0;A = [1,2],B = [3,4]→2.5
🧭 從讀題到解法
- 拆解：要求 O(log)，所以「合併後排序取中」O(m+n) 或雙指針都不夠快。
- 瓶頸：中位數 = 把合併陣列切成「左半、右半」，左半每個 ≤ 右半每個，且左半長度固定。問題是我們不想真的合併。
- 關鍵洞察（對分割點二分）：只要決定「在 A 切在哪」（取
i個給左半），B 的切點j就被左半總長度(m+n+1)//2唯一決定。正確的分割必須滿足A[i-1] ≤ B[j]且B[j-1] ≤ A[i]（左半最大 ≤ 右半最小）。i太大就左移、太小就右移——這對i是單調的，可以二分。 - 最優解：在較短的陣列上二分
i（保證 O(log(min(m,n)))），邊界用 ±∞ 哨兵處理。
def findMedianSortedArrays(A, B):
if len(A) > len(B): # binary search on the shorter array
A, B = B, A
m, n = len(A), len(B)
half = (m + n + 1) // 2 # size of the left half
lo, hi = 0, m
while lo <= hi:
i = lo + (hi - lo) // 2 # cut in A: i elements on the left
j = half - i # cut in B is forced
Aleft = A[i-1] if i > 0 else float('-inf')
Aright = A[i] if i < m else float('inf')
Bleft = B[j-1] if j > 0 else float('-inf')
Bright = B[j] if j < n else float('inf')
if Aleft <= Bright and Bleft <= Aright: # correct partition
if (m + n) % 2:
return float(max(Aleft, Bleft)) # odd total
return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
elif Aleft > Bright: # cut A is too far right
hi = i - 1
else: # cut A is too far left
lo = i + 1
double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
if (A.size() > B.size()) swap(A, B); // search the shorter one
int m = A.size(), n = B.size(), half = (m + n + 1) / 2;
int lo = 0, hi = m;
while (lo <= hi) {
int i = lo + (hi - lo) / 2; // cut in A
int j = half - i; // cut in B is forced
long Aleft = i > 0 ? A[i-1] : LONG_MIN;
long Aright = i < m ? A[i] : LONG_MAX;
long Bleft = j > 0 ? B[j-1] : LONG_MIN;
long Bright = j < n ? B[j] : LONG_MAX;
if (Aleft <= Bright && Bleft <= Aright) {
if ((m + n) % 2) return max(Aleft, Bleft);
return (max(Aleft, Bleft) + min(Aright, Bright)) / 2.0;
} else if (Aleft > Bright) hi = i - 1;
else lo = i + 1;
}
return 0.0;
}
- 複雜度：時間 O(log(min(m, n)))，空間 O(1)。
- 坑：① 一定要在較短陣列上二分，否則
j可能變負；② 邊界（切在最左/最右）用 ±∞ 哨兵，省掉一堆 if；③half = (m+n+1)//2搭配奇數時回傳max(左半)，一條式子同時處理奇偶。這題是 Hard，能講清楚「為什麼分割點可二分」就已贏一半。
一張表記住全部
| 題 | 二分對象 | while / 收斂 | 時間 | 關鍵 / 坑 |
|---|---|---|---|---|
| LC 704 | 已排序陣列 | lo<=hi, hi=mid-1 | O(log n) | 防溢位、閉區間三者一致 |
| LC 33 | 旋轉陣列 | lo<=hi | O(log n) | 先判哪半有序再夾 target |
| LC 153 | 旋轉陣列邊界 | lo<hi, hi=mid | O(log n) | 跟 nums[hi] 比 |
| LC 875 | 答案空間 | lo<hi, hi=mid | O(n log max) | 單調可行性判斷 |
| LC 4 | 分割點 | lo<=hi | O(log min(m,n)) | 二分短陣列、±∞ 哨兵 |
面試辨識口訣
- 看到「已排序 + 找值 / 找邊界」→ 標準二分，先確定「找精確值（
lo<=hi）」還是「找邊界（lo<hi+hi=mid）」。 - 看到「旋轉排序陣列」→ 每次必有一半有序，判斷哪半、再決定收哪邊。
- 看到「最小的能…/最大的不超過… + 單調可行性」→ 對答案二分，搜尋空間是答案而非輸入。
- 看到「兩個排序陣列、要 O(log)」→ 二分分割點，記得搜短的那個。
二分搜尋的精髓不是「陣列排好了」，而是**「答案空間單調，所以每次能砍一半」**。先把 704 的模板焊進肌肉記憶，剩下四題都只是換了「二分的對象」而已。