CKTIS / C++
Linear search
Linear search checks successive elements without requiring sorting. In C++, std::find returns an iterator to the first match or the end iterator.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
std::find(first, last, value)Linear search checks successive elements until a match is found or the range is exhausted. The data need not be sorted.
Use std::find(first, last, value) from <algorithm>. The range [first, last) excludes last. The result is an iterator to the first element satisfying *it == value, not an index. No match, including an empty range, yields last; never dereference it.
For n elements, at most n comparisons are needed: worst-case cost is O(n). The example demonstrates duplicates and a missing value. Iterator subtraction gives a zero-based index because std::array provides random-access iterators.
The example targets C++23. The cited page is an evolving working draft, not a frozen C++23 publication.
Examples
#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";
}
}
}
Result
3: index 1 7: not found
The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.