Giao diện
🔍 Searching Algorithms
STL cung cấp nhiều search algorithms — từ linear search đơn giản đến binary search nhanh trên sorted data.
std::find — Linear Search
cpp
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {5, 2, 8, 1, 9, 3};
// Find value
auto it = std::find(v.begin(), v.end(), 8);
if (it != v.end()) {
std::cout << "Found 8 at index: " << (it - v.begin()) << std::endl;
} else {
std::cout << "Not found" << std::endl;
}
// Find in string
std::string s = "Hello World";
auto sit = std::find(s.begin(), s.end(), 'o');
// Points to first 'o'
return 0;
}Time Complexity: O(n)
std::find_if — Search with Predicate
cpp
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
// Tìm số chẵn đầu tiên > 5
auto it = std::find_if(v.begin(), v.end(), [](int x) {
return x % 2 == 0 && x > 5;
});
if (it != v.end()) {
std::cout << "Found: " << *it << std::endl; // 6
}
// std::find_if_not — tìm phần tử KHÔNG thỏa predicate
auto it2 = std::find_if_not(v.begin(), v.end(), [](int x) {
return x < 5;
});
// Points to 5 (first NOT < 5)std::count và std::count_if
cpp
std::vector<int> v = {1, 2, 2, 3, 2, 4, 2, 5};
// Count occurrences
int count = std::count(v.begin(), v.end(), 2);
std::cout << "Count of 2: " << count << std::endl; // 4
// Count with condition
int evenCount = std::count_if(v.begin(), v.end(), [](int x) {
return x % 2 == 0;
});
std::cout << "Even count: " << evenCount << std::endl; // 5Binary Search — O(log n)
⚠️ YÊU CẦU
Binary search algorithms chỉ hoạt động đúng với SORTED ranges!
std::binary_search
cpp
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
// Chỉ check tồn tại — không cho vị trí
bool found = std::binary_search(v.begin(), v.end(), 5);
// true
bool notFound = std::binary_search(v.begin(), v.end(), 10);
// falsestd::lower_bound
cpp
std::vector<int> v = {1, 2, 4, 4, 4, 6, 7};
// 0 1 2 3 4 5 6
// lower_bound: iterator tới phần tử ĐẦU TIÊN >= value
auto it = std::lower_bound(v.begin(), v.end(), 4);
// Points to index 2 (first 4)
auto it2 = std::lower_bound(v.begin(), v.end(), 5);
// Points to index 5 (6, vì 5 không tồn tại)
// Insert position để giữ sorted order
v.insert(std::lower_bound(v.begin(), v.end(), 5), 5);
// [1, 2, 4, 4, 4, 5, 6, 7]std::upper_bound
cpp
std::vector<int> v = {1, 2, 4, 4, 4, 6, 7};
// upper_bound: iterator tới phần tử ĐẦU TIÊN > value
auto it = std::upper_bound(v.begin(), v.end(), 4);
// Points to index 5 (6)
// Range of equal elements
auto low = std::lower_bound(v.begin(), v.end(), 4); // index 2
auto high = std::upper_bound(v.begin(), v.end(), 4); // index 5
int count = high - low; // 3 (số lượng 4s)std::equal_range
cpp
std::vector<int> v = {1, 2, 4, 4, 4, 6, 7};
// Trả về pair(lower_bound, upper_bound)
auto [low, high] = std::equal_range(v.begin(), v.end(), 4);
std::cout << "First 4 at: " << (low - v.begin()) << std::endl; // 2
std::cout << "Past last 4: " << (high - v.begin()) << std::endl; // 5
std::cout << "Count: " << (high - low) << std::endl; // 3Binary Search Visualization
┌─────────────────────────────────────────────────────────────────┐
│ BINARY SEARCH BOUNDS │
├─────────────────────────────────────────────────────────────────┤
│ │
│ v = [1, 2, 4, 4, 4, 6, 7] │
│ 0 1 2 3 4 5 6 │
│ │
│ lower_bound(4): ──────────▼ │
│ [1, 2, 4, 4, 4, 6, 7] │
│ ^ │
│ index 2 │
│ │
│ upper_bound(4): ──────────▼ │
│ [1, 2, 4, 4, 4, 6, 7] │
│ ^ │
│ index 5 │
│ │
│ equal_range: [lower, upper) │
│ ^──────^ │
│ index 2 to 5 │
│ │
└─────────────────────────────────────────────────────────────────┘
]all_of, any_of, none_of
cpp
std::vector<int> v = {2, 4, 6, 8, 10};
// Tất cả đều chẵn?
bool allEven = std::all_of(v.begin(), v.end(), [](int x) {
return x % 2 == 0;
}); // true
// Có số > 5?
bool hasGreater = std::any_of(v.begin(), v.end(), [](int x) {
return x > 5;
}); // true (6, 8, 10)
// Không có số âm?
bool noNegative = std::none_of(v.begin(), v.end(), [](int x) {
return x < 0;
}); // truestd::search — Find Subsequence
cpp
std::vector<int> haystack = {1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<int> needle = {4, 5, 6};
auto it = std::search(haystack.begin(), haystack.end(),
needle.begin(), needle.end());
if (it != haystack.end()) {
std::cout << "Found at index: " << (it - haystack.begin()) << std::endl;
// Found at index: 3
}Binary Search với Custom Comparator
cpp
struct Person {
std::string name;
int age;
};
std::vector<Person> people = {
{"Alice", 25},
{"Bob", 30},
{"Charlie", 35},
{"David", 40}
};
// Sorted by age!
// Find person with age 30
auto it = std::lower_bound(people.begin(), people.end(), 30,
[](const Person& p, int age) {
return p.age < age;
});
if (it != people.end() && it->age == 30) {
std::cout << "Found: " << it->name << std::endl; // Bob
}Performance Comparison
| Algorithm | Time | Requirement |
|---|---|---|
std::find | O(n) | None |
std::find_if | O(n) | None |
std::binary_search | O(log n) | Sorted! |
std::lower_bound | O(log n) | Sorted! |
std::upper_bound | O(log n) | Sorted! |
std::equal_range | O(log n) | Sorted! |
📚 Tổng kết
| Algorithm | Returns | Use Case |
|---|---|---|
find | Iterator to element | Unsorted, find exact value |
find_if | Iterator to element | Find with condition |
binary_search | bool | Check existence (sorted) |
lower_bound | Iterator | First >= value (sorted) |
upper_bound | Iterator | First > value (sorted) |
equal_range | pair of iterators | Range of equal values |
➡️ Tiếp theo
Tiếp theo: Transform & Reduce — Functional operations.