查找算法分類
| 算法 | 用途 | 複雜度 | 備註 |
|---|
find | 查找單一值 | O(n) | 通用，線性掃描 |
find_if | 條件查找 | O(n) | 配合謂詞/函數對象 |
search_n | 查找 n 次重複值 | O(n*m) | |
search | 查找子序列 | O(n*m) | |
find_end | 查找子序列最後出現位置 | O(n*m) | |
find_first_of | 查找集合中任一元素首次出現 | O(n*m) | |
adjacent_find | 查找相鄰重複元素 | O(n) | |
binary_search | 有序區間二分查找 | O(log n) | 需有序 |
lower_bound | 首個不小於 value 位置 | O(log n) | 有序區間 |
upper_bound | 首個大於 value 位置 | O(log n) | 有序區間 |
equal_range | 等值範圍 [lower, upper) | O(log n) | 有序區間 |
關鍵選擇原則
- 關聯式容器 (
set/map 等) 自帶 find() 成員函數，紅黑樹實現 O(log n)，優先使用。
- string 自帶
find()，優化過，優先使用。
- 已排序序列（
vector、deque 等）使用 binary_search 族。
- 無序序列通用查找用
find/find_if。
實戰範例
1. find 多次查找同一值
list lst = {1,2,3,4,5,6,7,8, 1,2,3,4,5,6,7,8};
auto p1 = find(lst.begin(), lst.end(), 4);
auto p2 = (p1 != lst.end()) ? find(next(p1), lst.end(), 4) : lst.end();
if (p1 != lst.end() && p2 != lst.end()) {
--p1; ++p2;
for (auto it = p1; it != p2; ++it) cout << *it; // 輸出 3 4 5 6 7 8 1 2 3
}
2. find_if 配合函數對象與適配器
vector v = {1,2,3,4,5,6,7,8,9};
// 查找第一個 > 3 的元素
auto p = find_if(v.begin(), v.end(), bind2nd(greater(), 3)); // 輸出 4
// 查找第一個不能被 3 整除的元素
p = find_if(v.begin(), v.end(), not1(bind2nd(modulus(), 3))); // 輸出 1
現代 C++ (C++11+) 建議用 Lambda 替代 bind2nd/not1：
auto p = find_if(v.begin(), v.end(), [](int x){ return x > 3; });
auto p = find_if(v.begin(), v.end(), [](int x){ return x % 3 != 0; });
3. 關聯容器與 string 專用查找
set s = {43, 78, -1, 124}; // 自動排序
auto it = s.find(78); // O(log n)，紅黑樹查找
if (it != s.end()) cout << "Found: " << *it;
string str = "AnnaBelle";
auto pos = str.find("Belle"); // 返回 3
if (pos != string::npos) cout << "Found at " << pos;
預定義函數對象速查
| 算術 | 關係 | 邏輯 |
|---|
plus<T> | equal_to<T> | logical_and<T> |
minus<T> | not_equal_to<T> | logical_or<T> |
multiplies<T> | less<T> | logical_not<T> |
divides<T> | greater<T> | |
modulus<T> | less_equal<T> | |
negate<T> | greater_equal<T> | |
適配器
bind1st(op, val) / bind2nd(op, val)：綁定二元運算符一個參數。not1(unary_pred) / not2(binary_pred)：邏輯取反。ptr_fun / mem_fun：函數指針/成員函數適配為函數對象。
