Linear Search

Linear search is a foundational algorithmic technique used to find a target value within a sequential data structure. It operates by sequentially inspecting each element of the collection from the beginning until the target is matched or the collection is exhausted. While theoretically inefficient for large datasets compared to logarithmic alternatives like binary search, linear search remains the optimal access pattern for unstructured or unsorted collections, linked lists lacking random-access iterators, and hardware contexts where cache locality and branching predictability dictate actual wall-clock performance.

#include <vector>
#include <optional>
#include <concepts>

template<typename T>
requires std::equality_comparable<T>
class LinearSearchEngine {
public:
    explicit LinearSearchEngine(const std::vector<T>& dataset) : data(dataset) {}
    [[nodiscard]] std::optional<size_t> find(const T& target) const;
private:
    const std::vector<T>& data;
};

template<typename T>
requires std::equality_comparable<T>
std::optional<size_t> LinearSearchEngine<T>::find(const T& target) const {
    for (size_t i = 0; i < data.size(); ++i) {
        if (data[i] == target) {
            return i;
        }
    }
    return std::nullopt;
}

#include <iostream>
#include <cassert>

int main() {
    std::vector<int> numbers = {10, 23, 45, 70, 11, 15};
    LinearSearchEngine<int> engine(numbers);

    assert(engine.find(70) == 3);
    assert(engine.find(10) == 0);
    assert(engine.find(15) == 5);
    assert(engine.find(999) == std::nullopt);

    std::cout << "All linear search assertions passed successfully." << std::endl;
    return 0;
}

// For thread-safe searches over concurrent collections, ensure read locks or atomic snapshots are utilized.
// Avoid linear search inside tight performance loops if dataset size N scales dynamically; migrate to hash-based indices (O(1)) or balanced trees (O(log n)).

Mathematical Formulation & Complexity Analysis

Let D be a finite sequence (array or list) of elements x_0, x_1, …, x_(n-1) of size n. Given a target query t, the linear search function f(D, t) evaluates the predicate p(x_i) = (x_i == t) sequentially for i = 0, 1, 2, … until p(x_i) evaluates to true or i = n.

– Worst-case Time Complexity: O(n). Occurs when the target t does not exist in D, or exists exclusively at the final index x_(n-1), requiring n full predicate evaluations.
– Average-case Time Complexity: O(n). Assuming uniform distribution and that the target exists within D with probability p, the expected number of comparisons is roughly (n + 1) / 2.
– Best-case Time Complexity: O(1). Occurs when the target matches the initial element x_0.
– Space Complexity: O(1) auxiliary space. Linear search operates strictly in-place without requiring additional dynamic memory allocations or call stack growth beyond constant registers.

Hardware-Level Optimization & Cache Locality

In modern CPU architectures, memory latency heavily dominates computational complexity. While asymptotic analysis classifies linear search as O(n) and binary search as O(log n), linear search frequently outperforms binary search on small-to-medium array sizes (typically n < 64 or when elements fit within CPU cache lines). This occurs because linear search accesses contiguous memory addresses sequentially, maximizing hardware prefetcher efficiency and L1/L2 cache hit rates. Binary search, conversely, exhibits non-contiguous memory jump patterns that induce frequent cache misses and pipeline stalls.