二分搜尋 — Binary Search 三種模板與二分答案技巧 | 資料結構與演算法
2026/06/21
二分搜尋（Binary Search） 是面試中最常考、卻也最容易在邊界條件上翻車的演算法。掌握三種模板的不變量、理解 二分答案 的思維轉換，你會發現這個看似簡單的技法能解決一大類「在有序空間上找邊界」的難題。
前言
猜一個 1 到 100 的整數，每次猜一個數字，對方只告訴你「太大」或「太小」。你會怎麼猜？
幾乎所有人的直覺都是：先猜 50，再根據回饋猜 25 或 75，以此類推。這就是 二分搜尋 的核心思想——利用 單調性（Monotonicity） 每次排除一半的可能性，最多只需 ⌈log₂100⌉ = 7 次就能猜到答案。
二分搜尋的時間複雜度是 O(log n)，但它真正難的地方從來不是「把範圍縮半」這個概念，而是在實作時稍一不慎就會寫出死迴圈或遺漏邊界的 bug。本文的目標是讓你徹底理解三種模板的差異，並掌握「二分答案」這個能將一大類優化問題化繁為簡的通用技法。
本文學習要點：
- 三種模板（精確搜尋、
lower_bound、upper_bound）的不變量與實作 mid計算的溢位防護與向上/向下取整選擇- 二分答案的思維框架（最小化最大值 vs 最大化最小值）
- 旋轉陣列搜尋與矩陣搜尋
- 五大常見陷阱與面試考點
核心概念：搜尋空間與不變量
搜尋空間必須具有單調性
二分搜尋能成立的前提：搜尋空間必須具有某種有序或單調的性質，使得在每一步都能判斷目標在左半還是右半，從而合法地排除一半。
最直觀的例子是已排序的整數陣列。但「有序性」的範圍遠不止於此——任何滿足「某個條件在某個閾值之前全為 false，之後全為 true（或反之）」的問題，都可以用二分搜尋來處理。
三種模板的對比
| 模板 | 目的 | 搜尋區間 | 循環條件 | 返回值 |
|---|---|---|---|---|
| 標準二分 | 找目標是否存在，返回索引 | 閉區間 [lo, hi] | lo <= hi | 索引或 -1 |
| lower_bound | 找第一個 >= target 的位置 | 半開區間 [lo, hi) | lo < hi | 插入點（左邊界） |
| upper_bound | 找第一個 > target 的位置 | 半開區間 [lo, hi) | lo < hi | 插入點（右邊界） |
關鍵洞察：三種模板最大的差別不是邏輯，而是「搜尋區間的定義」。閉區間 [lo, hi] 需要 lo <= hi 才能確保單元素也被檢查；半開區間 [lo, hi) 則用 lo < hi 表示 hi 已是安全的「哨兵」位置。混用兩種風格是 bug 的根源。
搜尋收斂過程圖解
以在 [1, 3, 5, 7, 9, 11, 13] 中搜尋 7 為例，一步就找到：
index: 0 1 2 3 4 5 6
value: [1, 3, 5, 7, 9, 11, 13]
^ ^
lo=0 hi=6
^
mid=3 → arr[3]=7 == target ✓ 找到！
以 lower_bound 在含重複元素的 [1, 3, 7, 7, 7, 9, 11] 中找第一個 7：
Step 1: lo=0, hi=7, mid=3 → arr[3]=7 == target → hi=mid=3（保留 mid，不排除）
Step 2: lo=0, hi=3, mid=1 → arr[1]=3 < target → lo=mid+1=2
Step 3: lo=2, hi=3, mid=2 → arr[2]=7 == target → hi=mid=2
Step 4: lo=2 == hi=2 → 終止，返回 lo=2 ✓（第一個 7 的位置）
以 upper_bound 在同一陣列中找最後一個 7 之後的位置：
Step 1: lo=0, hi=7, mid=3 → arr[3]=7 <= target → lo=mid+1=4（向右壓縮）
Step 2: lo=4, hi=7, mid=5 → arr[5]=9 > target → hi=mid=5
Step 3: lo=4, hi=5, mid=4 → arr[4]=7 <= target → lo=mid+1=5
Step 4: lo=5 == hi=5 → 終止，返回 lo=5 ✓（最後一個 7 在 index 4，即 lo-1）
JavaScript / TypeScript 實作
模板一：標準二分搜尋
適用於元素唯一、確認是否存在的場景。使用閉區間 [lo, hi]。
/**
* 標準二分搜尋：找到返回索引，找不到返回 -1
* 前提：nums 已排序，元素不重複
* 搜尋區間：閉區間 [lo, hi]
*/
function binarySearch(nums: number[], target: number): number {
let lo = 0;
let hi = nums.length - 1; // 閉區間，hi 指向最後一個元素
while (lo <= hi) { // 等號確保單元素 [x, x] 也會被檢查
// 防止 (lo + hi) 整數溢位，右移1位等同除以2
const mid = lo + ((hi - lo) >> 1);
if (nums[mid] === target) {
return mid; // 精確命中
} else if (nums[mid] < target) {
lo = mid + 1; // mid 已確認不是答案，向右縮
} else {
hi = mid - 1; // mid 已確認不是答案，向左縮
}
}
return -1; // lo > hi，搜尋空間耗盡
}
// 測試
console.log(binarySearch([1, 3, 5, 7, 9, 11, 13], 7)); // 3
console.log(binarySearch([1, 3, 5, 7, 9, 11, 13], 6)); // -1
console.log(binarySearch([5], 5)); // 0（單元素）
console.log(binarySearch([5], 3)); // -1
模板二：左邊界搜尋（lower_bound）
找第一個 >= target 的位置。使用半開區間 [lo, hi)，hi 初始化為 nums.length（哨兵值）。
/**
* lower_bound：找第一個 >= target 的位置
* 若所有元素都 < target，返回 nums.length
* 含重複元素時，返回第一個等於 target 的索引
* 搜尋區間：半開區間 [lo, hi)
*/
function lowerBound(nums: number[], target: number): number {
let lo = 0;
let hi = nums.length; // 半開區間，hi 不參與比較
while (lo < hi) { // 不用等號，lo==hi 時區間為空即停止
const mid = lo + ((hi - lo) >> 1);
if (nums[mid] < target) {
lo = mid + 1; // mid 肯定不是答案（< target），安全排除
} else {
hi = mid; // mid 可能是答案（>= target），保留它
}
}
return lo; // lo == hi，即第一個 >= target 的插入點
}
// 測試
const arr = [1, 3, 7, 7, 7, 9, 11];
console.log(lowerBound(arr, 7)); // 2（第一個7在 index 2）
console.log(lowerBound(arr, 6)); // 2（6應插在 index 2）
console.log(lowerBound(arr, 0)); // 0（插在最前面）
console.log(lowerBound(arr, 12)); // 7（超出尾端，等於 length）
模板三：右邊界搜尋（upper_bound）
找第一個 > target 的位置。與 lower_bound 的唯一差異是條件從 < target 改為 <= target。
/**
* upper_bound：找第一個 > target 的位置
* 含重複元素時，返回最後一個等於 target 的索引+1
* 搭配 lowerBound 可確定 target 在陣列中的完整範圍 [lb, ub)
*/
function upperBound(nums: number[], target: number): number {
let lo = 0;
let hi = nums.length;
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (nums[mid] <= target) { // 注意：<= 而非 <，這是與 lowerBound 唯一的差異
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
/**
* 計算 target 在排序陣列中出現的次數
* [lowerBound, upperBound) 即為 target 的出現範圍
*/
function countOccurrences(nums: number[], target: number): number {
return upperBound(nums, target) - lowerBound(nums, target);
}
// 測試
const arr2 = [1, 3, 7, 7, 7, 9, 11];
console.log(upperBound(arr2, 7)); // 5（返回5，最後一個7在 index 4）
console.log(countOccurrences(arr2, 7)); // 3（共3個7）
console.log(countOccurrences(arr2, 5)); // 0（無5）
旋轉陣列搜尋
旋轉排序陣列（Rotated Sorted Array）是 [4, 5, 6, 7, 0, 1, 2] 這樣的結構——陣列被「旋轉」過，整體不再有序，但關鍵洞察是：旋轉後的陣列，以 mid 為界，至少有一半是完全有序的。
/**
* 旋轉陣列二分搜尋（LeetCode 33）
* 每次判斷哪半段是有序的，再判斷 target 是否在有序那側
*/
function searchRotated(nums: number[], target: number): number {
let lo = 0;
let hi = nums.length - 1;
while (lo <= hi) {
const mid = lo + ((hi - lo) >> 1);
if (nums[mid] === target) return mid;
// 判斷左半段 [lo, mid] 是否有序
if (nums[lo] <= nums[mid]) {
// 左半段有序：target 在 [nums[lo], nums[mid]) 範圍內才往左找
if (nums[lo] <= target && target < nums[mid]) {
hi = mid - 1;
} else {
lo = mid + 1; // target 不在有序的左側，去右側找
}
} else {
// 右半段有序 [mid, hi]：target 在 (nums[mid], nums[hi]] 範圍內才往右找
if (nums[mid] < target && target <= nums[hi]) {
lo = mid + 1;
} else {
hi = mid - 1; // target 不在有序的右側，去左側找
}
}
}
return -1;
}
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 0)); // 4
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 3)); // -1
console.log(searchRotated([1], 0)); // -1
二分答案框架：最小化最大值
二分答案的核心思路：不直接求最優解，而是對答案本身做二分，然後用 check 函數判斷該答案是否可行。
當問題具有「答案越大越容易滿足條件」的單調性時，可以用左邊界二分找最小可行答案。
/**
* 二分答案：最小化最大值
* LeetCode 410 — Split Array Largest Sum
* 問題：將 nums 分成 k 段，使每段和的最大值最小，求此最小最大值
*/
function splitArrayLargestSum(nums: number[], k: number): number {
// 答案下界：最大單個元素（每段至少一個元素，不可能比最大元素更小）
let lo = Math.max(...nums);
// 答案上界：所有元素總和（k=1 時全部在一段）
let hi = nums.reduce((a, b) => a + b, 0);
// check：每段和的上限為 maxSum 時，能否分成 <= k 段？
const canSplit = (maxSum: number): boolean => {
let segments = 1;
let currentSum = 0;
for (const num of nums) {
if (currentSum + num > maxSum) {
segments++; // 開新段
currentSum = num;
if (segments > k) return false; // 超出限制，不可行
} else {
currentSum += num;
}
}
return true;
};
// 找最小的 maxSum 使得 canSplit 為 true → 左邊界二分
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (canSplit(mid)) {
hi = mid; // mid 可行，嘗試更小的答案
} else {
lo = mid + 1; // mid 不可行，答案必須更大
}
}
return lo;
}
console.log(splitArrayLargestSum([7, 2, 5, 10, 8], 2)); // 18
console.log(splitArrayLargestSum([1, 2, 3, 4, 5], 2)); // 9
二分答案框架：最大化最小值
當問題具有「答案越小越容易滿足條件」的單調性時，改用右邊界二分找最大可行答案。注意 mid 要向上取整以避免無窮迴圈。
/**
* 二分答案：最大化最小值
* LeetCode 875 — Koko Eating Bananas（Koko 吃香蕉）
* 問題：以速度 k 每小時吃香蕉，要在 h 小時內吃完所有堆，求最小速度 k
*/
function minEatingSpeed(piles: number[], h: number): number {
let lo = 1; // 速度最小為 1
let hi = Math.max(...piles); // 速度最大為最大那堆（一小時吃完一堆就夠）
// check：速度 k 能否在 h 小時內吃完所有堆？
const canFinish = (k: number): boolean => {
let hours = 0;
for (const pile of piles) {
hours += Math.ceil(pile / k); // 每堆向上取整（吃不完就算一小時）
}
return hours <= h;
};
// 找最小可行速度 → 左邊界二分
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (canFinish(mid)) {
hi = mid; // mid 可行，嘗試更小的速度
} else {
lo = mid + 1; // mid 不可行，速度必須更大
}
}
return lo;
}
console.log(minEatingSpeed([3, 6, 7, 11], 8)); // 4
console.log(minEatingSpeed([30, 11, 23, 4, 20], 5)); // 30
C++ 對照
STL 標準庫：直接使用
C++ 的 <algorithm> 頭文件已內建 binary_search、lower_bound、upper_bound 三個函數，效率與手刻相同，且語義清晰。
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main() {
vector<int> nums = {1, 3, 7, 7, 7, 9, 11};
int target = 7;
// binary_search：只判斷是否存在，返回 bool
bool found = binary_search(nums.begin(), nums.end(), target);
cout << "found: " << found << "\n"; // 1 (true)
// lower_bound：第一個 >= target 的迭代器，轉換成索引
auto lb = lower_bound(nums.begin(), nums.end(), target);
cout << "lower_bound index: " << (lb - nums.begin()) << "\n"; // 2
// upper_bound：第一個 > target 的迭代器
auto ub = upper_bound(nums.begin(), nums.end(), target);
cout << "upper_bound index: " << (ub - nums.begin()) << "\n"; // 5
// 計算出現次數（upper - lower 的距離）
cout << "count: " << (ub - lb) << "\n"; // 3
// equal_range：同時返回 [lower_bound, upper_bound)，更簡潔
auto [lo, hi] = equal_range(nums.begin(), nums.end(), target);
cout << "range: [" << (lo - nums.begin())
<< ", " << (hi - nums.begin()) << ")\n"; // [2, 5)
return 0;
}
手刻實作（對照 STL）
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
// 手刻 lower_bound
int myLowerBound(const vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size(); // 半開區間 [lo, hi)
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
// 手刻 upper_bound（唯一差異：<= 而非 <）
int myUpperBound(const vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] <= target) lo = mid + 1;
else hi = mid;
}
return lo;
}
// 二分答案：Koko 吃香蕉（LeetCode 875）
int minEatingSpeed(vector<int>& piles, int h) {
int lo = 1;
int hi = *max_element(piles.begin(), piles.end());
// Lambda 作為 check 函數（C++14+）
auto canFinish = [&](int k) -> bool {
long long hours = 0;
for (int pile : piles)
hours += (pile + k - 1) / k; // 上取整：(a + b - 1) / b
return hours <= h;
};
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (canFinish(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
// 旋轉陣列搜尋（LeetCode 33）
int searchRotated(vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
if (nums[lo] <= nums[mid]) { // 左半段有序
if (nums[lo] <= target && target < nums[mid])
hi = mid - 1;
else
lo = mid + 1;
} else { // 右半段有序
if (nums[mid] < target && target <= nums[hi])
lo = mid + 1;
else
hi = mid - 1;
}
}
return -1;
}
複雜度分析
| 操作 | 時間複雜度 | 空間複雜度 | 說明 |
|---|---|---|---|
| 標準二分（精確搜尋） | O(log n) | O(1) | 每次縮半，最多 ⌈log₂n⌉ 步 |
| lower_bound | O(log n) | O(1) | 找第一個 ≥ target 的位置 |
| upper_bound | O(log n) | O(1) | 找第一個 > target 的位置 |
| 旋轉陣列二分 | O(log n) | O(1) | 每次至少排除一半 |
| 矩陣二分（m×n） | O(log(m×n)) | O(1) | 展開為一維後做標準二分 |
| 二分答案 | O(log(range) × T_check) | O(1)～O(n) | T_check 為 check 函數複雜度 |
變體與延伸
浮點數二分
當答案是實數時（例如求平方根、找函數零點），不能用整數邏輯判斷終止。兩種常見策略：
// 策略一：固定迭代次數（100次後精度已達 1e-15）
function sqrtByBinarySearch(x: number): number {
let lo = 0, hi = x;
for (let iter = 0; iter < 100; iter++) {
const mid = (lo + hi) / 2;
if (mid * mid <= x) lo = mid;
else hi = mid;
}
return lo;
}
// 策略二：設定精度閾值（適合對精度有明確要求的場景）
function findZero(f: (x: number) => number, lo: number, hi: number): number {
// 前提：f(lo) < 0，f(hi) > 0
while (hi - lo > 1e-9) {
const mid = (lo + hi) / 2;
if (f(mid) < 0) lo = mid;
else hi = mid;
}
return (lo + hi) / 2;
}
console.log(sqrtByBinarySearch(2).toFixed(6)); // 1.414214
三分搜尋（Ternary Search）
當函數是單峰（先遞增後遞減，或先遞減後遞增）時，三分搜尋能找到極值點。每次將搜尋範圍縮減為 2/3。
/**
* 三分搜尋：在 [lo, hi] 區間找單峰函數的最大值位置
* 每次比較 m1 = lo + (hi-lo)/3 和 m2 = hi - (hi-lo)/3
*/
function ternarySearch(
f: (x: number) => number,
lo: number,
hi: number,
epsilon = 1e-9
): number {
while (hi - lo > epsilon) {
const m1 = lo + (hi - lo) / 3;
const m2 = hi - (hi - lo) / 3;
if (f(m1) < f(m2)) lo = m1; // 最大值在 [m1, hi]
else hi = m2; // 最大值在 [lo, m2]
}
return (lo + hi) / 2;
}
// 找 f(x) = -(x-3)^2 + 9 的極值（在 x=3 時取最大值 9）
const peakX = ternarySearch(x => -(x - 3) ** 2 + 9, 0, 10);
console.log(peakX.toFixed(4)); // 3.0000
二分答案的經典問題類型
| 問題類型 | 代表題目 | 二分對象 | check 函數 |
|---|---|---|---|
| 最小化最大值 | LeetCode 410、875 | 最大值上限 | 貪心驗證是否可分 |
| 最大化最小值 | LeetCode 1552、2226 | 最小值下限 | 貪心驗證能否放足夠多 |
| 第 k 小/大 | LeetCode 378、668 | 答案的值 | 計算 ≤ mid 有多少個 |
| 找第一個壞版本 | LeetCode 278 | 版本號 | 呼叫 API 判斷是否為壞版本 |
面試考點
陷阱一：mid 計算整數溢位
在 C++ 或 Java 中，int 的上限約 21 億。當 lo 和 hi 都接近這個值時，lo + hi 會溢位。
// 錯誤：(lo + hi) 可能溢位
const mid = (lo + hi) / 2; // ❌
// 正確：用差值計算
const mid = lo + Math.floor((hi - lo) / 2); // ✓
const mid = lo + ((hi - lo) >> 1); // ✓（位元運算，與上行等價）
陷阱二：最大化問題的無窮迴圈
在「最大化最小值」的二分答案中，若 mid 向下取整且 check 為 true 時執行 lo = mid，當 lo 和 hi 只差 1 時會陷入無窮迴圈：
// 問題重現：lo=2, hi=3
// 向下取整：mid = 2 + floor((3-2)/2) = 2 + 0 = 2
// 若 canPlace(2) 為 true → lo = mid = 2（lo 沒變！無窮迴圈）
// 解法：最大化問題的 mid 向上取整
const mid = lo + Math.ceil((hi - lo) / 2);
// 或等價：
const mid = lo + ((hi - lo + 1) >> 1); // ✓
// 這樣：lo=2, hi=3 → mid = 2 + ceil(1/2) = 3
// 若 canPlace(3) 為 true → lo = 3 = hi（迴圈終止）✓
記憶口訣：最小化問題（找最小可行值）用向下取整；最大化問題（找最大可行值）用向上取整。
陷阱三：搜尋區間不一致導致 off-by-one
// 標準二分（閉區間）：
let lo = 0, hi = nums.length - 1; // hi 指向最後一個元素
while (lo <= hi) { /* ... */ } // 等號確保單元素 [x] 被處理
// lower_bound（半開區間）：
let lo = 0, hi = nums.length; // hi 是哨兵，不對應實際元素
while (lo < hi) { /* ... */ } // 無等號，lo==hi 時結束
// ❌ 危險：混用 hi = nums.length - 1 但用 lo < hi
// 當 target 比所有元素都大時，會遺漏最後一個元素的比較！
陷阱四：旋轉陣列判斷有序側忘記等號
// ❌ 錯誤：lo == mid 時（單元素情況）判斷失效
if (nums[lo] < nums[mid]) { /* ... */ }
// ✓ 正確：包含等號，lo == mid 時左側就是 [lo] 本身，仍是有序的
if (nums[lo] <= nums[mid]) { /* ... */ }
陷阱五：浮點數二分用整數終止條件
// ❌ 永不收斂（浮點數的 lo 和 hi 可能永遠不相等）
while (lo < hi) { /* ... */ }
// ✓ 固定迭代次數
for (let iter = 0; iter < 100; iter++) { /* ... */ }
// ✓ 精度閾值
while (hi - lo > 1e-9) { /* ... */ }
LeetCode 練習
LeetCode 704 — Binary Search（Easy）
最純粹的標準二分。給定排序陣列和 target，返回索引或 -1。直接套用模板一即可。
function search(nums: number[], target: number): number {
let lo = 0, hi = nums.length - 1;
while (lo <= hi) {
const mid = lo + ((hi - lo) >> 1);
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)
LeetCode 34 — Find First and Last Position of Element in Sorted Array（Medium）
找目標在陣列中的起始和結束位置，經典的 lower_bound + upper_bound 組合。
function searchRange(nums: number[], target: number): number[] {
// lower_bound 找左邊界，upper_bound 找右邊界
const lb = lowerBound(nums, target);
// 若 lb 越界或對應元素不等於 target，表示不存在
if (lb === nums.length || nums[lb] !== target) return [-1, -1];
// upper_bound 返回的是右邊界的「下一個」位置，減1才是最後一個 target
return [lb, upperBound(nums, target) - 1];
}
console.log(searchRange([5, 7, 7, 8, 8, 10], 8)); // [3, 4]
console.log(searchRange([5, 7, 7, 8, 8, 10], 6)); // [-1, -1]
// 時間 O(log n)，空間 O(1)
LeetCode 33 — Search in Rotated Sorted Array（Medium）
旋轉陣列搜尋，需判斷哪半段有序。詳見上方「旋轉陣列搜尋」一節。
解題關鍵：每次先用 nums[lo] <= nums[mid] 判斷左半段是否有序，再根據有序那側的邊界值決定 target 在哪邊，最後縮減搜尋範圍。時間 O(log n)，空間 O(1)。
LeetCode 875 — Koko Eating Bananas（Medium）
二分答案入門題。速度越快越容易在時限內完成（單調性），對速度做左邊界二分，找最小可行速度。詳見上方「二分答案框架：最小化最大值」一節中的實作。時間 O(n × log(max(piles)))，空間 O(1)。
LeetCode 410 — Split Array Largest Sum（Hard）
二分答案進階題。將陣列分成 k 段，最小化各段和的最大值。思路：對「最大值的上限」做左邊界二分，check 函數用貪心（線性掃描判斷能否在此上限下完成分割）。詳見上方的完整實作。時間 O(n × log(sum))，空間 O(1)。
總結
二分搜尋的「難」從來不在於演算法本身，而在於實作細節的精確性。回顧本文的核心知識點：
三種模板各司其職：標準二分（閉區間，找精確值）、
lower_bound（半開區間，找左插入點）、upper_bound（半開區間，找右插入點）。選定一種風格後，嚴格遵守其區間定義，不要混用。mid計算要防溢位：始終使用lo + ((hi - lo) >> 1)（向下取整）或lo + ((hi - lo + 1) >> 1)（向上取整，用於最大化問題）。二分答案是一種思維轉換：當優化問題的答案具有單調性（可行性隨答案單調變化），就把「求最優解」轉化為「對答案的值做二分 + check 函數驗證」。識別這個轉換是解題的關鍵。
五大陷阱要牢記：溢位、最大化問題的向上取整、區間不一致、旋轉陣列的等號、浮點數終止條件。
二分搜尋的精髓在於「對有序空間的精確分割」。一旦你真正理解不變量的概念，就能將這個思維套用到更廣泛的問題上——從陣列邊界查找，到答案空間的最優化，再到資料庫索引的範圍查詢，都是同一套思想的延伸。
希望這篇文章能幫助你徹底掌握二分搜尋，在面試時寫出沒有 bug 的實作。如果有任何問題或疑惑，歡迎至 聯絡頁面 留言交流。
下一篇預告：我們將進入 二元樹（Binary Tree） 的世界，探討樹的遍歷、深度/廣度優先搜尋，以及如何在遞迴與迭代之間靈活切換。