🔍
Какой алгоритм поиска выбрать?Выбор неправильного алгоритма поиска может в разы замедлить программу.
✏️
Выбираем по ситуации:1️⃣
Неупорядоченные данные → std::find (O(n)):std::vector<int> nums = {3, 1, 4, 1, 5};
auto it = std::find(nums.begin(), nums.end(), 4);
if (it != nums.end()) {
std::cout << "Found at position " << std::distance(nums.begin(), it);
}2️⃣
Упорядоченные данные → std::binary_search (O(log n)):std::vector<int> sorted_nums = {1, 2, 3, 4, 5};
if (std::binary_search(sorted_nums.begin(), sorted_nums.end(), 3)) {
std::cout << "Found!";
}3️⃣
Частые поиски → std::unordered_set (O(1) average):std::unordered_set<int> lookup = {1, 3, 5, 7, 9};
if (lookup.find(5) != lookup.end()) {
std::cout << "Found instantly!";
}4️⃣
Поиск с предикатом → std::find_if:auto even = std::find_if(nums.begin(), nums.end(),
[](int n) { return n % 2 == 0; });
❌
Частая ошибка: Использование find на отсортированных данных.
Библиотека C/C++ разработчика #буст