Linear search

Linear search checks values one at a time until it finds the target or reaches the end. It works on unsorted input and can be adapted to arrays, linked lists and streams. Unlike binary search, it does not assume random access or sorted order.

Step-by-step example

Given [7, 4, 9, 2] and a target of 9, the search compares 7, then 4, then 9. The first matching index is 2 using zero-based indexing. Searching for 5 checks all four values and returns -1 to indicate no match.

C# and C++ implementations

C#

C# | LinearSearch.cs

public static int FindIndex(int[] values, int target)
{
    ArgumentNullException.ThrowIfNull(values);
    for (int i = 0; i < values.Length; i++)
    {
        if (values[i] == target) return i;
    }
    return -1;
}

C++

C++ | LinearSearch.cpp

#include <vector>
#include <cstddef>

int findIndex(const std::vector<int>& values, int target) {
    for (std::size_t i = 0; i < values.size(); ++i) {
        if (values[i] == target) return static_cast<int>(i);
    }
    return -1;
}
// For collections larger than INT_MAX, use an optional<size_t> result.

Both functions scan from left to right and return the first matching index. The C# version checks for null input; the C++ version uses a reference to a vector, which is assumed to exist. The C++ int return type is convenient for small vectors, but may overflow for enormous collections; a production API can use std::optional<std::size_t> instead of -1.

Runtime and memory

Case	Comparisons	Bound
First value matches	1	O(1) best-case time
Target at the last index	n	O(n) worst-case time
Target missing	n	O(n) worst-case time

If a target is uniformly distributed among n positions and guaranteed to exist, the expected number of comparisons is approximately (n + 1) / 2: still O(n). That average-case assumption does not apply to every real dataset. Both implementations use O(1) auxiliary space. If you collect all matching indices, output space grows with the number of matches.

Correctness and edge cases

For an empty collection, return -1 without indexing. For duplicates, return the first occurrence. If the input is already sorted and supports efficient random access, binary search reduces worst-case comparisons to O(log n) after accounting for the sorted-input precondition.

Try it: Use [4, 4, 8, 11, 4]. Predict the index when searching for 4, 8 and 7, and count comparisons for each. Then compare with the Big O explorer.