基本概念 #
二分搜的概念不難，在一個排序好的陣列裡找目標值，每次砍掉一半範圍
不過要特別注意一定需要排序好的陣列
假設有一個陣列：
陣列：[1, 3, 5, 7, 9, 11, 13]
如果我們要找 7，第一步找它的中點 mid = index 3 = 7 找到了！
再一個如果，但這次換成找 6
- 第一步：mid = index 3 = 7，6 < 7 → 往左找 [1,3,5]
- 第二步：mid = index 1 = 3，6 > 3 → 往右找 [5]
- 第三次：mid = index 2 = 5，6 ≠ 5 → 找不到
看起來很簡單對吧！那麼程式改怎麼寫呢？
二分搜尋 — 找特定目標的位置 #
比如說我要從 [1, 3, 5, 7, 9, 11, 13] 找出 5 的所在位置的 index，就可以使用下面的寫法
int binary_search(vector<int>& arr, int target) {
int lo = 0, hi = arr.size() - 1;
while (lo <= hi) { // 注意：<=
int mid = lo + (hi - lo) / 2; // 不用 (lo+hi)/2，防止溢位
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
lo = mid + 1;
else
hi = mid - 1;
}
return -1; // 找不到
}
舉例 #
程式也許有點難理解，所以舉個例子：
arr = {1, 3, 5, 7, 9};
target = 9;
第一步： #
lo = 0, hi = 4, mid=2
---
index: 0 1 2 3 4
arr = {1, 3, 5, 7, 9};
^ ^ ^
l m h
---
mid=2 -> arr[2] = 5 < 9
更新
lo = mid + 1 = 3, hi = 4
---
index: 0 1 2 3 4
arr = {1, 3, 5, 7, 9};
^ ^
l h
第二步： #
lo = 3, hi = 4, mid = 3
---
index: 0 1 2 3 4
arr = {1, 3, 5, 7, 9};
^ ^
l h
---
mid=3 -> arr[3] = 7 < 9
更新
lo = mid + 1 = 4, hi = 4
---
index: 0 1 2 3 4
arr = {1, 3, 5, 7, 9};
^
h、L
找到目標，回傳 mid （4）
二分搜尋 — 找「第一個 ≥ target」的位置（lower_bound） #
int lower_bound(vector<int>& arr, int target) {
int lo = 0, hi = arr.size(); // 注意：hi = size()，不是 size()-1
while (lo < hi) { // 注意：< 不是 <=
int mid = lo + (hi - lo) / 2;
if (arr[mid] < target)
lo = mid + 1;
else
hi = mid; // 注意：不是 mid-1
}
return lo;
}
舉例 #
比如說要找 :
陣列：[1, 3, 3, 3, 3, 3, 5, 7, 9, 11, 13]
target : 3
那麼程式會回傳 index = 1，因為陣列的第 1 個位置即元素為 3，是第一個大於等於 3 的元素
我們一個一個步驟慢慢來看
arr = {1, 3, 3, 3, 3, 3, 5, 7, 9, 11, 13}
target : 3
lo = 0, hi = 11
mid = 5 （向下取整）
arr = {1, 3, 3, 3, 3, 3, 5, 7, 9, 11, 13}
^ ^ ^
l m h
因為 arr [5] == 3 >= target：3
所以，hi = mid = 5
arr = {1, 3, 3, 3, 3, 3, 5, 7, 9, 11, 13}
^ ^
l h
mid = 2
因為 arr [2] == 3 >= target:3
所以，hi = mid = 2
arr = {1, 3, 3, 3, 3, 3, 5, 7, 9, 11, 13}
^ ^
l h
mid = 1
因為 arr [1] == 2 >= target:3
所以，hi = mid = 1
arr = {1, 3, 3, 3, 3, 3, 5, 7, 9, 11, 13}
^ ^
l h
mid = 0
因為 arr [0] == 1 < target:3
所以，lo = mid + 1 = 1
arr = {1, 3, 3, 3, 3, 3, 5, 7, 9, 11, 13}
^
l,h
這時候因為迴圈條件寫的是 lo < hi 所以會跳出去，回傳 lo
找不到 #
那如果找不到呢 ？ 比如：
陣列：[1, 3, 5, 7, 9, 11, 13]
target : 114514
程式最終會發生：
lo == hi
但 hi 從來沒被動過，因為目標值太大了
這個時候會回傳的就是陣列的大小
為什麼是 hi = mid？而非 hi = mid -1 #
假設：
arr[mid] >= target
例如:
arr[mid] = 5
target = 4
那麼
5 已經符合 >= 4
因此
mid 有可能就是答案
所以不能
hi = mid - 1;
因為這麼做會把答案丟掉，必須
hi = mid;
保留他
找「第一個 > target」的位置（upper_bound） #
int upper_bound(vector<int>& arr, int target) {
int lo = 0, hi = arr.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] <= target) // 只有這行和 lower_bound 不同
lo = mid + 1;
else
hi = mid;
}
return lo;
}
舉例 #
陣列：[1, 3, 3, 3, 3, 3, 5, 7, 9, 11, 13]
target : 3
arr = {1, 3, 3, 3, 3, 3, 5, 7, 9, 11, 13}
target : 3
lo = 0, hi = 11
mid = 5 （向下取整）
arr = {1, 3, 3, 3, 3, 3, 5, 7, 9, 11, 13}
^ ^ ^
l m h
因為 arr [5] == 3 <= target：3
所以，lo = mid + 1 = 6
arr = {1, 3, 3, 3, 3, 3, 5, 7, 9, 11, 13}
^ ^
l h
mid = 8
因為 arr [8] == 9 > target：3
所以 hi = mid = 8
arr = {1, 3, 3, 3, 3, 3, 5, 7, 9, 11, 13}
^ ^
l h
mid = 7
因為 arr [7] == 7 > target：3
所以，hi = mid = 7
arr = {1, 3, 3, 3, 3, 3, 5, 7, 9, 11, 13}
^ ^
l h
mid = 6
因為 arr [6] == 5 > target：3
所以，hi = mid = 6
這時，因為 hi == lo == 6 迴圈中斷，回傳 lo
和 lower_bound 比較 #
比如要找
arr = {1,3,3,3,5,7}
target : 3
lower_bound(arr, 3) 找第一個 >= 3 會是：
1 3 3 3 5 7
↑
而 upper_bound(arr, 3) 找第一個 > 3會是
1 3 3 3 5 7
↑
這時可以發現，
upper_bound - lower_bound
就是：
等於 target 的元素個數
以上面的例子來看， 4 - 1 = 3 ，而 3 剛好有 3 個
C ++ STL 的 upper_bound 和 lower_bound #
前面提到的 upper_bound 和 lower_bound 這兩個玩意兒，實際上 C++ 的 STL 已經準備好這兩個東西了！
那就是：
lower_bound(first, last, target) → 第一個 >= target 的位置
upper_bound(first, last, target) → 第一個 > target 的位置
比如
陣列： {1, 3, 3, 3, 5, 7}
^ ^
l u
找 3：
lower_bound → index 1 （第一個 >= 3）
upper_bound → index 4 （第一個 > 3）
基本用法 #
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v = {1, 3, 3, 3, 5, 7};
// lower_bound / upper_bound回傳的是 iterator
auto lb = lower_bound(v.begin(), v.end(), 3);
auto ub = upper_bound(v.begin(), v.end(), 3);
cout << *lb << "\n"; // 3（iterator 指向的值）
cout << lb - v.begin() << "\n"; // 1（index） 用 減去 v.begin() 轉成 index
cout << ub - v.begin() << "\n"; // 4（index）
// 3 出現的次數
cout << ub - lb << "\n"; // 3
}
這裡的 iterator 可以想像成類似指標的東西（但不完全是指標）你可以把它想成：
「能夠指向容器元素，並透過
*、++等操作遍歷容器的物件」
.begin() 和 .end() 以及 lower_bound() 、 upper_bound 回傳的也都是 iterator
找不存在值的情況 #
vector<int> v = {1, 3, 5, 7};
// 找 4
auto lb = lower_bound(v.begin(), v.end(), 4);
cout << *lb << "\n"; //輸出是 5（第一個 >= 4 的數）
cout << lb - v.begin() << "\n"; // 2（index）
// 找 9（比所有數都大）
auto lb2 = lower_bound(v.begin(), v.end(), 9);
if (lb2 == v.end())
cout << "不存在\n"; // 回傳 end()，要檢查！
如果找不到目標，lower_bound() 或 upper_bound() 會回傳 .end() 所以透過 if (lb2 == v.end()) 就可以知道沒有找到目標
常見用法 #
1. 判斷某個值是否存在 #
vector<int> v = {1, 3, 5, 7};
int target = 5;
auto it = lower_bound(v.begin(), v.end(), target);
if (it != v.end() && *it == target)
cout << "存在\n";
else
cout << "不存在\n";
2. 找嚴格小於 target 的最大值 #
vector<int> v = {1, 3, 5, 7};
auto it = lower_bound(v.begin(), v.end(), 5); // 此時 *it = 5
if (it != v.begin()) {
--it;
cout << *it << "\n"; // 3（最大的 < 5 的數）
}
3. 找嚴格小於等於 target 的最大值 #
vector<int> v = {1, 3, 5, 7};
auto it = upper_bound(v.begin(), v.end(), 5); //此時 *it = 7
if (it != v.begin()) {
--it;
cout << *it << "\n"; // 5（最大的 <= 5 的數）
}
4. 統計某個值出現次數 #
vector<int> v = {1, 3, 3, 3, 5};
int cnt = upper_bound(v.begin(), v.end(), 3) - lower_bound(v.begin(), v.end(), 3);
cout << cnt << "\n"; //輸出為 3
用在 set 和 map
#
set / map 有自己的成員函數版本，必須用成員函數，不能用全域版本：
set<int> s = {1, 3, 5, 7};
// ✔ 用成員函數，O(log n)
auto it = s.lower_bound(3);
// ❌ 用全域函數，set 不支援隨機存取，會變 O(n)
auto it = lower_bound(s.begin(), s.end(), 3);
總結 #
陣列： [ 1, 3, 3, 3, 5, 7 ]
↑ ↑
lower_bound(3) upper_bound(3)
「第一個 >= 3」 「第一個 > 3」
it == v.end() → 所有元素都小於 target
lower == upper → target 不存在（但有插入位置）
upper - lower → target 出現次數
*(--lower_bound) → 嚴格小於 target 的最大值
*(--upper_bound) → 小於等於 target 的最大值
