Knowledge baseExam Center
ENEnglish
Choose language13

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.

Sources