Библиотека C/C++ разработчика | cpp, boost, qt

🔍 Какой алгоритм поиска выбрать?

Выбор неправильного алгоритма поиска может в разы замедлить программу.


✏️ Выбираем по ситуации:

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++ разработчика

#буст

Please open Telegram to view this post

VIEW IN TELEGRAM

🔥10👍1

www.tgoop.com/cppproglib/6088

2.62K viewsedited  Sep 24 at 13:22

🔍 Какой алгоритм поиска выбрать?

Выбор неправильного алгоритма поиска может в разы замедлить программу.


✏️ Выбираем по ситуации:

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);
}

std::vector<int> sorted_nums = {1, 2, 3, 4, 5};
if (std::binary_search(sorted_nums.begin(), sorted_nums.end(), 3)) {
    std::cout << "Found!";
}

std::unordered_set<int> lookup = {1, 3, 5, 7, 9};
if (lookup.find(5) != lookup.end()) {
    std::cout << "Found instantly!";
}

auto even = std::find_if(nums.begin(), nums.end(), 
                        [](int n) { return n % 2 == 0; });