База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C++

Линейно търсене

Линейното търсене проверява последователни елементи, без да изисква данните да са сортирани. В C++ std::find връща итератор към първото съвпадение или крайния итератор.

Версия: C++23; repository compiler flag, production runtime not attested

Синтаксис

std::find(first, last, value)

Линейното търсене (linear search) проверява последователни елементи, докато намери съвпадение или изчерпи диапазона. Данните не е необходимо да са сортирани.

Използвайте std::find(first, last, value) от <algorithm>. Диапазонът [first, last) не включва last. Резултатът е итератор към първия елемент, за който е изпълнено *it == value, а не индекс. Ако няма съвпадение, включително при празен диапазон, резултатът е last; никога не го дереферирайте.

За n елемента са нужни най-много n сравнения: сложността в най-лошия случай е O(n). Примерът показва дублиращи се стойности и липсваща стойност. Изваждането на итератори дава индекс, започващ от нула, тъй като std::array предоставя итератори с произволен достъп.

Примерът е предназначен за C++23. Цитираната страница е развиващ се работен проект, а не окончателна публикация на C++23.

Примери

#include <algorithm>
#include <array>
#include <iostream>

int main() {
    const std::array<int, 5> values{8, 3, 6, 3, 9};
    for (int target : {3, 7}) {
        const auto it = std::find(values.begin(), values.end(), target);
        std::cout << target << ": ";
        if (it != values.end()) {
            std::cout << "index " << (it - values.begin()) << '\n';
        } else {
            std::cout << "not found\n";
        }
    }
}

Резултат

3: index 1
7: not found

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници