Linear Search — Implement linear search over arrays/vectors - C Plus Plus

SECTION 1

Historical Context & Motivation

The problem of locating a specific item within a collection is one of the oldest and most fundamental tasks in computing. Before digital computers existed, librarians, census takers, and record-keepers performed what was essentially a linear search every time they scanned through a ledger or card catalogue entry by entry, comparing each record against the one they sought. When the first stored-program computers emerged in the late 1940s and early 1950s, this same sequential scan became the very first search algorithm programmed into their instruction sets. The simplicity of the approach—examine element 0, then element 1, and so on—meant that it required no special data arrangement and could be coded in just a handful of machine instructions.

As data sets grew, computer scientists began to formalize the costs of searching. Donald Knuth's landmark work, The Art of Computer Programming (1968), devoted extensive analysis to sequential searching, rigorously establishing its average- and worst-case behavior and comparing it against logarithmic alternatives. The development of the C++ Standard Template Library in the 1990s codified linear search as std::find, making it a first-class citizen alongside more sophisticated algorithms. Understanding linear search remains essential because it forms the baseline against which all other search algorithms are measured.

1945 • Stored-Program Searching

Von Neumann's EDVAC design enables programs that iterate through memory cells sequentially, implementing the first machine-level linear searches.

1962 • Sentinel Search Optimization

Researchers introduce the sentinel value technique, eliminating one branch per iteration and reducing the constant factor in sequential search loops.

1968 • Knuth's Formal Analysis

Volume 3 of The Art of Computer Programming provides rigorous average-case analysis of sequential search, establishing (n + 1)/2 comparisons for a successful lookup.

1994 • C++ STL std::find

Alexander Stepanov's STL ships with std::find, a generic linear search over iterator ranges, adopted into the C++ standard library.

2020s • Ranges & Constexpr Search

C++20 Ranges and constexpr evaluation enable compile-time linear searches and composable pipelines such as std::ranges::find.

The central question this lesson addresses is deceptively simple: given an unsorted or arbitrarily ordered collection of n elements, how do we locate a target value, and what are the precise costs of doing so? By studying linear search, you establish the analytical vocabulary—comparisons, best case, worst case, average case—that you will apply to every algorithm you encounter hereafter.

SECTION 2

Core Principles & Definitions

Linear search, also known as sequential search, operates under a straightforward contract: starting from the first element of a container, it inspects each element in order, comparing it against a target value (sometimes called the key). The algorithm terminates as soon as it finds a match or exhausts all elements. Despite its conceptual simplicity, implementing it correctly in C++ involves several important design decisions—choosing between raw arrays and std::vector, deciding on return types, and handling edge cases such as empty containers or duplicate matches.

Sequential Traversal

The algorithm visits elements in index order (0, 1, 2, …, n−1). No random access pattern, no skipping—every element before the target must be inspected.

Equality Comparison

Each iteration performs a single comparison using operator== (or a user-supplied predicate). The comparison is the algorithm's elementary operation for complexity analysis.

No Precondition on Order

Unlike binary search, linear search imposes no requirement that the data be sorted. This makes it applicable to any iterable container regardless of element ordering.

Early Termination

Upon finding a match, the algorithm returns immediately. In the best case this occurs at index 0 with a single comparison; in the worst case, at index n−1 or after scanning all n elements without a match.

O(1) Auxiliary Space

Linear search requires only a constant amount of extra memory—an index variable and the target value—making it an in-place algorithm with no additional data structure overhead.

✦

KEY TAKEAWAY

Think of linear search like scanning a bookshelf from left to right looking for a particular title. You have no index, no alphabetical ordering—just your eyes moving sequentially along each spine. If the book is the very first one, you're done instantly; if it's the last one (or not there at all), you inspect every single spine. This captures the essence of the best- and worst-case behavior: the absence of structural information forces exhaustive inspection.

SECTION 3

Visual Explanation — Tracing a Linear Search

The following diagram illustrates a linear search for the target value 42 within an array of eight integers. Each row represents one iteration: the current index is highlighted, and the comparison result is shown on the right. Observe how the algorithm progresses strictly left to right, performing one comparison per step until the match is found at index 5.

Each row represents one loop iteration. Red-highlighted cells indicate a mismatch; the green cell at step 5 marks the successful match. Dashed cells represent elements already inspected and skipped in previous iterations.

Notice that the algorithm performed exactly 6 comparisons to locate the target at index 5 (indices 0 through 5 inclusive). Had the target been absent, the algorithm would have inspected all 8 elements and returned a sentinel value (such as −1 or an end iterator). This visual pattern—a sliding window of inspection moving from left to right—directly maps to the loop structure you will write in C++.

SECTION 4

Mathematical Framework — Complexity Analysis

To reason formally about linear search, we define n as the number of elements in the array (or vector) and count the number of key comparisons as the fundamental unit of work. In asymptotic analysis, we characterize the algorithm's resource consumption using Big-O, Big-Ω, and Big-Θ notation.

BEST CASE

T_best(n) = 1 comparison ⟹ Ω(1)

The target is at index 0. A single comparison suffices, giving constant-time performance in the best case.

WORST CASE

T_worst(n) = n comparisons ⟹ O(n)

The target is at the last position or is absent entirely. Every element must be inspected, yielding linear growth in the number of comparisons.

AVERAGE CASE (SUCCESSFUL SEARCH)

T_avg(n) = (1 + 2 + 3 + … + n) / n = (n + 1) / 2 ⟹ Θ(n)

Assuming the target is equally likely to be at any of the n positions, the expected number of comparisons is the arithmetic mean of 1 through n. Although the constant factor is ½, the growth rate remains linear, so the average case is Θ(n).

SPACE COMPLEXITY

S(n) = O(1)

Linear search uses a constant number of auxiliary variables (an index counter and possibly a temporary for the target), independent of the input size.

The derivation of the average case merits closer attention. If the target is at position i (0-indexed), then i + 1 comparisons are needed. Under the uniform distribution assumption, each position has probability 1/n, so the expected value is Σ(i + 1)/n for i = 0 to n − 1, which simplifies to (n + 1)/2. For an unsuccessful search, the algorithm always performs exactly n comparisons—there is no early termination. Both successful and unsuccessful average cases are Θ(n), but the constant differs by a factor of roughly 2.

💡

Why O(n) Is Not Always Bad

For small collections (n < ~64), the overhead of setting up a more complex algorithm like binary search—including the prerequisite of sorting—often exceeds the cost of a simple sequential scan. Modern CPUs also benefit from the cache-friendly, predictable memory access pattern of linear search over contiguous arrays. Always consider the constant factors and hardware effects alongside asymptotic growth rates.

SECTION 5

Implementation Variants in C++

C++ offers multiple idiomatic ways to implement linear search, each suited to different use cases. The choice between a raw array with pointer arithmetic, a std::vector with index-based access, and iterator-based STL calls affects not only readability and safety but also how naturally the code generalizes to other containers. Below we examine the three primary variants and their trade-offs.

Variant 1 — Index-Based Search on a Raw Array

The most traditional form accepts a C-style array pointer and a size parameter. The function returns the index of the first occurrence or −1 as a sentinel for "not found." While concise, this approach requires the caller to pass the size separately, which is a common source of bugs.

📝

Raw Array Implementation

int linearSearch(const int arr[], int n, int target) {
    for (int i = 0; i < n; ++i) {
        if (arr[i] == target)
            return i;
    }
    return -1;
}

Variant 2 — std::vector with Index-Based Access

Using std::vector<int> eliminates the need for a separate size parameter, since the container carries its own size via .size(). Returning std::optional<std::size_t> (C++17) is a safer alternative to the −1 sentinel, explicitly encoding the possibility of failure in the type system.

📝

Vector + std::optional Implementation

#include <vector>
#include <optional>

std::optional<std::size_t> linearSearch(
    const std::vector<int>& vec, int target) {
    for (std::size_t i = 0; i < vec.size(); ++i) {
        if (vec[i] == target)
            return i;
    }
    return std::nullopt;
}

Variant 3 — STL Iterator-Based (std::find)

The STL's std::find (declared in <algorithm>) is a generic linear search parameterized by iterators. It works on any container that exposes forward iterators—arrays, vectors, lists, deques—and returns an iterator to the found element or end() if absent. In C++20, std::ranges::find offers a range-based overload that further simplifies the call site.

📝

STL std::find Usage

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {15, 27, 8, 63, 11, 42, 9, 33};
    auto it = std::find(v.begin(), v.end(), 42);
    if (it != v.end())
        std::cout << "Found at index "
                  << std::distance(v.begin(), it) << '\n';
    else
        std::cout << "Not found\n";
}

The flowchart shows the two decision points in every linear search: the bounds check (i < n) and the equality comparison (arr[i] == target). The green path represents matches; the red path represents mismatches or exhaustion.

Variant	Return Type	Container	Key Advantage
Raw array + index	`int` (−1 sentinel)	`int[]`	Minimal overhead; compatible with C APIs
`std::vector` + optional	`std::optional<size_t>`	`std::vector<T>`	Type-safe "not found"; carries size internally
`std::find` (STL)	Iterator (`end()` sentinel)	Any iterable	Generic; works on lists, deques, arrays, etc.

Comparison of C++ linear search implementation variants

SECTION 6

Worked Example — Searching a Vector of Strings

Let us trace a complete example that goes beyond integers. Suppose we have a std::vector<std::string> containing course codes, and we want to find the index of "CS301". This example demonstrates the template-based approach and shows how the algorithm generalizes to non-numeric types.

Linear Search for "CS301" in a Vector of Strings

1
Step 1 — Define the Data

We declare a vector of five course codes: {"MA101", "PH202", "CS301", "EE110", "CH150"}. The target is "CS301" and n = 5.
2
Step 2 — Write the Template Function

We write a generic version: template<typename T> std::optional<std::size_t> linearSearch(const std::vector<T>& vec, const T& target). This template works for any type T that supports operator==.
3
Step 3 — Iteration 0 (i = 0)

Compare vec[0] = "MA101" with "CS301". The strings differ at position 0 ('M' ≠ 'C'). No match; increment i.

"MA101" ≠ "CS301" → continue
4
Step 4 — Iteration 1 (i = 1)

Compare vec[1] = "PH202" with "CS301". Mismatch at position 0 ('P' ≠ 'C'). No match; increment i.

"PH202" ≠ "CS301" → continue
5
Step 5 — Iteration 2 (i = 2)

Compare vec[2] = "CS301" with "CS301". All characters match. The function returns std::optional<std::size_t>{2}.

Match found at index 2 after 3 comparisons
6
Step 6 — Verify the Result

The caller tests the returned optional: if (auto idx = linearSearch(courses, target); idx.has_value()). Since the optional contains a value, we safely dereference it to obtain index 2. The total work was 3 comparisons out of a possible 5, illustrating a case between best (1) and worst (5).

Output: "Found CS301 at index 2"

SECTION 7

Strengths, Limitations & When to Use Linear Search

No algorithm exists in isolation; understanding when to reach for linear search—and when to avoid it—is as important as knowing how to implement it. The table below summarizes the principal advantages and drawbacks, followed by guidance on situational usage.

Strengths	Limitations
No preconditions — works on unsorted, unordered data.	O(n) worst/average case — prohibitively slow for large datasets.
O(1) space — no auxiliary data structures needed.	No exploitation of order — cannot leverage sorting to skip elements.
Simple to implement and debug — minimal code surface for bugs.	Not cache-optimal on linked lists — only cache-friendly on contiguous storage.
Works on any container type — only requires forward iteration.	Repeated queries are expensive — for m queries, total cost is O(m × n).
Fast for small n — constant factors often beat logarithmic methods for n < ~64.	No partial-match support — for range queries or nearest-neighbor, other structures (trees, hashing) are superior.

Strengths vs. Limitations of Linear Search

⚖️

WHEN TO USE LINEAR SEARCH

Think of linear search as the Swiss army knife in your algorithmic toolkit—not the most efficient tool for any single task, but universally applicable. Use it when the collection is small, unsorted, or when you expect to search only once or a few times. If you find yourself performing repeated searches on the same data, that's a signal to invest in sorting (for binary search) or hashing (for O(1) lookups). The break-even point where sorting + binary search outperforms repeated linear searches is approximately n × log(n) + m × log(n) < m × n, where m is the number of queries.

SECTION 8

Connection to Advanced Search Algorithms

Linear search serves as the conceptual and analytical baseline against which every more sophisticated search algorithm is measured. Understanding its O(n) cost provides the motivation for the logarithmic and constant-time alternatives that you will study next. The table below positions linear search within the broader landscape of search algorithms, illustrating the trade-offs between preconditions, time complexity, and space overhead.

Algorithm	Time (Average)	Precondition	Space
Linear Search	Θ(n)	None	O(1)
Binary Search	Θ(log n)	Sorted array	O(1)
Hash Table Lookup	Θ(1) amortized	Hash function + table	O(n)
Balanced BST Search	Θ(log n)	BST invariant maintained	O(n)
Interpolation Search	O(log log n) for uniform data	Sorted + uniformly distributed	O(1)

Comparison of common search algorithms

A key insight from this comparison is the precondition–performance trade-off: every algorithm that beats O(n) search time demands some structural guarantee about the data—sorted order, a hash function, or a tree invariant. Maintaining these structures has its own cost (sorting is O(n log n), building a hash table is O(n)), which must be amortized over multiple queries to justify the investment. Linear search, requiring no such precondition, remains the rational choice when the data is ephemeral or queries are infrequent.

Looking forward, you will find that many advanced algorithms—including sentinel linear search (which eliminates one branch per iteration by placing the target at the end), self-organizing lists (move-to-front or transpose heuristics), and SIMD-accelerated search (comparing multiple elements per instruction using SSE/AVX intrinsics)—are optimizations that preserve the O(n) asymptotic bound but improve the constant factor or cache behavior of linear search.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why linear search is said to have Θ(n) average-case complexity for a successful search, even though the best case is O(1). In your answer, clarify the distinction between Big-O, Big-Ω, and Big-Θ as they apply to this algorithm.

Show answer

Big-O provides an upper bound, Big-Ω provides a lower bound, and Big-Θ provides a tight bound (both upper and lower). The best case of O(1) describes a specific input scenario (target at index 0), not the algorithm's general behavior. For the average case under uniform distribution, the expected number of comparisons is (n + 1)/2, which grows linearly with n. Since this expression is both O(n) and Ω(n), the average case is Θ(n). The Θ notation tells us that no matter how we analyze the typical case, linear growth is inherent—it is neither pessimistically overstated nor optimistically understated.

Question 2: BASIC CALCULATION

An array contains 200 elements. Assuming the target is present and equally likely to be at any position, what is the expected number of comparisons for a successful linear search? What if the target is absent?

Show answer

For a successful search with uniform probability, the expected number of comparisons is (n + 1)/2 = (200 + 1)/2 = 100.5 comparisons. This means on average, you inspect about half the array. For an unsuccessful search, the algorithm must examine every element to confirm the target is absent, so it always performs exactly n = 200 comparisons. Notice that the unsuccessful case is roughly twice as expensive as the average successful case, which directly follows from the (n + 1)/2 versus n relationship.

Question 3: INTERMEDIATE

Write a C++ function template that performs linear search on a std::vector<T> using a user-supplied predicate (a callable that takes const T& and returns bool) instead of equality comparison. Return an iterator to the first matching element or vec.end() if not found. What STL algorithm does this mirror?

Show answer

The function mirrors std::find_if. An implementation would be:

template<typename T, typename Pred>
auto linearSearchIf(std::vector<T>& vec, Pred pred) {
    for (auto it = vec.begin(); it != vec.end(); ++it)
        if (pred(*it)) return it;
    return vec.end();
}

This approach decouples the search logic from the comparison criterion, enabling searches like "find the first element greater than 50" via a lambda [](int x){ return x > 50; }. The complexity remains O(n) regardless of the predicate, since the algorithm structure is unchanged.

Question 4: APPLIED

A network monitoring system stores the last 1,000 packet timestamps in a circular buffer backed by a std::vector<uint64_t>. The system must check whether a specific timestamp exists in the buffer. Currently it uses linear search and handles up to 500 queries per second. If the system scales to 50,000 queries per second, explain whether linear search remains viable and propose an alternative data structure, justifying the trade-off.

Show answer

At 500 queries/sec with n = 1,000, linear search performs up to 500 × 1,000 = 500,000 comparisons per second, which is easily handled by modern CPUs. At 50,000 queries/sec, the worst-case comparison count rises to 50,000 × 1,000 = 50,000,000 comparisons per second. While still within CPU throughput limits for simple integer comparisons, the latency per query (up to 1,000 comparisons) may cause unacceptable jitter in a real-time system. A better approach would be to maintain a std::unordered_set<uint64_t> alongside the circular buffer. Insertions and deletions cost O(1) amortized, and lookups become O(1) amortized instead of O(n). The trade-off is O(n) additional space for the hash table and the complexity of keeping the set synchronized with the circular buffer's eviction policy.

Question 5: CRITICAL THINKING

Prove that any comparison-based search algorithm on an unsorted array of n distinct elements must examine at least n elements in the worst case to correctly determine that a target is absent. What does this tell us about the optimality of linear search for unsorted data?

Show answer

Suppose, for contradiction, that an algorithm A decides "target not found" after inspecting only k < n elements. Then there exists at least one uninspected position j. Construct an adversarial input where all inspected positions hold their original values, but position j holds the target. Algorithm A would still output "not found" on this modified input, which is incorrect. This contradiction proves that any correct algorithm must inspect all n elements in the worst case when the target is absent. This establishes that linear search's O(n) worst case for unsuccessful searches is optimal—no comparison-based algorithm can do better on unsorted data. The result is a direct consequence of the information-theoretic lower bound: without structural assumptions, you must gather information about every element.

SUMMARY

Linear Search — Summary

Summary

Linear search is the simplest and most universally applicable search algorithm: it examines each element of an array or std::vector in sequential order, comparing against a target value and returning upon the first match or after exhausting all elements. Its worst-case and average-case time complexity are both O(n), with a best case of O(1) when the target is at index 0. The algorithm requires O(1) auxiliary space and imposes no preconditions on the ordering of the data.

In C++, linear search can be implemented via index-based loops on raw arrays, std::optional return types with std::vector, or the generic std::find / std::find_if STL algorithms. While O(n) is optimal for unsorted data (as proven by an adversarial argument), sorted data enables binary search at O(log n), and hash-based structures achieve O(1) amortized lookups—each at the cost of additional preconditions or space. Mastering linear search establishes the analytical foundation for evaluating every search strategy you will encounter in your study of algorithms.