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
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.