Algorithm - Binary Search

Algorithm - Binary Search

LAVI
  2026-04-19 2026-04-19 Created   2026-05-05 2026-05-05 Updated      

Binary Search Note

Binary Search 的本質不是只用來找 sorted array 裡面的某個值

更精確地說：

  • Binary Search 是在一個具有單調性的搜尋空間中，每次排除一半不可能的答案

所謂單調性，通常可以轉換成一個布林序列：

1
2
3
F F F F T T T T
        ↑
   找第一個 True

或：

1
2
3
T T T T F F F F
      ↑
 找最後一個 True

因此，解 Binary Search 題目時，最重要的是先判斷：

  1. 搜尋空間是什麼？
  2. condition(mid) 是什麼？
  3. 要找第一個 True，還是最後一個 True？
  4. mid 還有沒有可能是答案？

Binary Search 題型總覽

題型 搜尋目標 模板
找某個值是否存在 target 是否在 array 中 while (left <= right)
找第一個滿足條件的位置 first true / lower bound / 最小可行解 while (left < right) 、 right = mid
找最後一個滿足條件的位置 last true / 最大可行解 while (left < right) 、 left = mid
根據趨勢找答案 peak / rotated minimum while (left < right)
Answer Binary Search 對答案範圍做二分 first true 或 last true

核心判斷原則

1. mid 還有沒有可能是答案？

這是決定更新方式的核心

判斷 更新方式 意義
mid 不可能是答案 left = mid + 1 或 right = mid - 1 直接丟掉 mid
mid 可能是答案 right = mid 或 left = mid 保留 mid

2. 如果使用 left = mid，mid 要偏右

更新方式 mid 寫法
right = mid int mid = left + (right - left) / 2;
left = mid int mid = left + (right - left + 1) / 2;

模板

模板一：找某個值是否存在

適用於：
在 sorted array 中找 target

例如：

  • Binary Search
  • Search in Rotated Sorted Array 中的局部找值
  • 傳統「有沒有 target」問題
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int binarySearch(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}
項目 說明
搜尋區間 [left, right]
while 條件 left <= right
為什麼用 <= 因為 left == right 時，還有一個元素需要檢查
更新方式 mid 若不是答案，就丟掉
回傳 找到回傳 index，找不到回傳 -1

模板二：找第一個滿足條件的位置

這是最常用的 Binary Search 模板

適用於：

  • lower_bound
  • upper_bound
  • search insert position
  • first true
  • 最小可行解
  • 最小速度
  • 最小容量
  • 最小天數
  • 最小答案

布林序列

1
2
3
F F F F T T T T
        ↑
   找第一個 True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int left = 0;
int right = n - 1;

while (left < right) {
    int mid = left + (right - left) / 2;

    if (condition(mid)) {
        right = mid;
    } else {
        left = mid + 1;
    }
}

return left;
項目 說明
搜尋區間 [left, right]
while 條件 left < right
目標 找第一個讓 condition(mid) == true 的位置
right = mid mid 可能是答案，所以保留
left = mid + 1 mid 不可能是答案，所以丟掉
mid 寫法 左中位數
回傳 left 或 right，兩者最後相同

lower_bound

例如:
找第一個 >= target 的位置
condition(mid) = nums[mid] >= target;

Search Insert Position 題型也是用這個模板

  • 如果找得到 target，回傳 target 的位置
  • 如果找不到 target，回傳第一個比 target 大的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int lowerBound(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size();

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

upper_bound

例如:
找第一個 > target 的位置
condition(mid) = nums[mid] > target;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int upperBound(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size();

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

模板三：找最後一個滿足條件的位置

適用於：

  • last true
  • 最大可行解
  • 最後一個小於等於 target 的位置
  • 最大可行值

布林序列

1
2
3
T T T T F F F F
      ↑
 找最後一個 True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int left = 0;
int right = n - 1;

while (left < right) {
    int mid = left + (right - left + 1) / 2;

    if (condition(mid)) {
        left = mid;
    } else {
        right = mid - 1;
    }
}

return left;
項目 說明
搜尋區間 [left, right]
while 條件 left < right
目標 找最後一個讓 condition(mid) == true 的位置
left = mid mid 可能是答案，所以保留
right = mid - 1 mid 不可能是答案，所以丟掉
mid 寫法 右中位數
為什麼 mid 要偏右 避免 left = mid 時死循環

例子：找最後一個 <= target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int lastLessEqual(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while (left < right) {
        int mid = left + (right - left + 1) / 2;

        if (nums[mid] <= target) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }

    return left;
}

有些題目不是在 array 裡二分，而是在「答案範圍」上二分

常見題型：

  • 最小速度
  • 最小容量
  • 最小天數
  • 最大距離
  • 最大甜度
  • 最小化最大值
  • 最大化最小值

判斷方式

如果題目問：
最小的 x，使得可以完成任務

通常是：

1
2
3
F F F F T T T T
        ↑
   找第一個 True

使用第一個 True 模板
如果題目問：
最大的 x，使得仍然可以完成任務

通常是：

1
2
3
T T T T F F F F
      ↑
 找最後一個 True

使用最後一個 True 模板

模板五：根據趨勢找答案

有些題目不是傳統 sorted array，也不是明顯的布林序列，但仍然可以透過局部趨勢排除一半

代表題目：

  • 162 Find Peak Element
  • 153 Find Minimum in Rotated Sorted Array
162. Find Peak Element 153. Find Minimum in Rotated Sorted Array

162. Find Peak Element

題目敘述中得知陣列中一定存在 peak
因此比較對象是：
nums[mid] 和 nums[mid + 1]

條件 說明 更新
nums[mid] > nums[mid + 1] 右邊是下降，peak 在左邊或 mid right = mid
nums[mid] < nums[mid + 1] 右邊是上升，peak 一定在右邊 left = mid + 1

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
};

left / right 初始化原則

核心原則

初始化範圍必須包含所有可能答案

題型 left right 原因
在 array 中找 target 0 n - 1 答案只能是合法 index
lower_bound / insert position 0 n 答案可能是 n，代表插在最後
first true in index range 0 n - 1 答案是某個合法 index
answer binary search 最小可能答案 最大可能答案 搜尋的是答案值，不一定是 index
peak element 0 n - 1 頭尾都可能是 peak

left <= right 和 left < right 的差別

寫法 常見用途 區間含義 特性
while (left <= right) 找 target 是否存在 [left, right] 每次都明確檢查 mid 是否為答案
while (left < right) 找邊界 / 收斂到答案 [left, right] 維持答案一定在區間內，最後收斂到 left == right

什麼時候用 left <= right

當題目是：
我要找某個明確 target
如果 nums[mid] == target，就可以直接 return

什麼時候用 left < right

當題目是：
我要找一個邊界
答案一直保留在 [left, right] 裡面
最後 left == right 就是答案

mid 寫法整理

目標 mid 更新方式
找第一個 True 左中位數 right = mid / left = mid + 1
找最後一個 True 右中位數 left = mid / right = mid - 1
找 target 左中位數即可 left = mid + 1 / right = mid - 1
Peak Element 左中位數 right = mid / left = mid + 1

常見題型判斷表

題目描述 關鍵字 單調性 使用模板
找 target 是否存在 find target, search target sorted array 找某個值
找 target 應插入位置 insert position nums[mid] >= target 第一個 True
找第一個大於等於 target lower_bound nums[mid] >= target 第一個 True
找第一個大於 target upper_bound nums[mid] > target 第一個 True
找最後一個小於等於 target last <= target nums[mid] <= target 最後一個 True
找最小速度 / 容量 / 天數 minimum, minimize, least 通常是 F F F T T 第一個 True
找最大距離 / 最大值 maximum, maximize, largest 通常是 T T T F F 最後一個 True
找 peak peak, greater than neighbors 根據斜率方向排除一半 趨勢二分
找 rotated sorted array 最小值 rotated, minimum 根據 mid 和 right 判斷哪邊有序 趨勢二分

面試時的判斷流程

Step 1：先判斷是不是找明確 target

如果題目是：
找 target 是否存在
找 target 的 index

使用：while (left <= right)

Step 2：如果不是找 target，判斷是不是找邊界

如果可以轉成：

1
F F F T T T

而且要找第一個 True
使用：

1
2
3
4
5
while (left < right)
mid = left + (right - left) / 2

if (condition(mid)) right = mid;
else left = mid + 1;

Step 3：如果可以轉成：

1
T T T F F F

而且要找最後一個 True

使用：

1
2
3
4
5
while (left < right)
mid = left + (right - left + 1) / 2

if (condition(mid)) left = mid;
else right = mid - 1;

Step 4：如果不是明顯布林序列，看能不能用趨勢排除一半

例如 Peak Element：

1
2
3
4
5
if (nums[mid] > nums[mid + 1]) {
    right = mid;
} else {
    left = mid + 1;
}

這類題目雖然不是 sorted array，但仍然可以 Binary Search，因為能根據趨勢判斷答案在哪一側

最後總結

問題類型 判斷方式 while mid 更新方式 回傳
找 target nums[mid] == target 可直接判斷 left <= right 左中位數 mid ± 1 找到回傳 index，否則 -1
找第一個 True F F F T T T left < right 左中位數 right = mid, left = mid + 1 left
找最後一個 True T T T F F F left < right 右中位數 left = mid, right = mid - 1 left
最小可行解 越大越容易成功 left < right 左中位數 can(mid) ? right = mid : left = mid + 1 left
最大可行解 越大越難成功 left < right 右中位數 can(mid) ? left = mid : right = mid - 1 left
Peak Element 看 nums[mid] 和 nums[mid + 1] 的趨勢 left < right 左中位數 下降 right = mid，上升 left = mid + 1 left

最短記憶版

找值：
while (left <= right)
mid 不是答案就丟掉

找第一個 True：
right = mid
left = mid + 1
mid 用左中位數

找最後一個 True：
left = mid
right = mid - 1
mid 用右中位數

初始化：
left / right 必須包含所有可能答案

更新：
mid 可能是答案，就保留 mid
mid 不可能是答案，就丟掉 mid

On this page
Algorithm - Binary Search
  1. Binary Search Note
  2. Binary Search 題型總覽
    1. 核心判斷原則
      1. 1. mid 還有沒有可能是答案？
      2. 2. 如果使用 left = mid，mid 要偏右
    2. 模板
      1. 模板一：找某個值是否存在
      2. 模板二：找第一個滿足條件的位置
      3. 模板三：找最後一個滿足條件的位置
      4. 模板四：Answer Binary Search
      5. 模板五：根據趨勢找答案
    3. left / right 初始化原則
      1. 核心原則
      2. left <= right 和 left < right 的差別
      3. 什麼時候用 left <= right
      4. 什麼時候用 left < right
      5. mid 寫法整理
    4. 常見題型判斷表
  3. 面試時的判斷流程
    1. Step 1：先判斷是不是找明確 target
    2. Step 2：如果不是找 target，判斷是不是找邊界
    3. Step 3：如果可以轉成：
    4. Step 4：如果不是明顯布林序列，看能不能用趨勢排除一半
  • 最後總結
    1. 最短記憶版