Linear Search

Linear search is the most direct answer to the question "is this value in the collection?" — visit each element in order until you find the target or run out of elements. No preconditions, no preprocessing, no tricks. Just a walk through the data.

Its simplicity is its strength. Any data, any order, any type that supports equality. The cost is that you may have to look at every element.

The Core Intuition

Imagine looking for a specific book on an unorganized shelf. You start at the left end and check each book one by one. If you find it, you stop. If you reach the right end without finding it, it is not there.

That is linear search. The structure of the data tells you nothing — you have no choice but to check each position.

Two outcomes per element:

• Match — return the index, stop searching.
• No match — advance to the next element.

One guarantee: if the element exists, you will find it. If it does not, you will confirm its absence after visiting every element.

Step-by-Step Trace

Array: [64, 25, 12, 22, 11], target: 22

Step 1: Compare arr[0] = 64 with target 22
  [64] [25] [12] [22] [11]
   ^
   i=0  →  64 ≠ 22, move right

Step 2: Compare arr[1] = 25 with target 22
  [64] [25] [12] [22] [11]
         ^
         i=1  →  25 ≠ 22, move right

Step 3: Compare arr[2] = 12 with target 22
  [64] [25] [12] [22] [11]
               ^
               i=2  →  12 ≠ 22, move right

Step 4: Compare arr[3] = 22 with target 22
  [64] [25] [12] [22] [11]
                  ^
                  i=3  →  22 == 22, FOUND at index 3

Three misses, one hit. The algorithm touched exactly 4 elements before returning.

What if the target were 99?

Step 1: i=0  →  64 ≠ 99
Step 2: i=1  →  25 ≠ 99
Step 3: i=2  →  12 ≠ 99
Step 4: i=3  →  22 ≠ 99
Step 5: i=4  →  11 ≠ 99
  i=5  →  i >= n, loop exits
  Return -1 (not found)

Every element was checked. This is the worst case.

Naive Implementation in Rust

fn linear_search(arr: &[i32], target: i32) -> i32 {
    for i in 0..arr.len() {       // iterate over every valid index
        if arr[i] == target {     // compare current element to target
            return i as i32;      // found: return the index as i32
        }
    }
    -1                            // target not found in the array
}
 
fn main() {
    let arr = [64, 25, 12, 22, 11];
    let target = 22;
 
    match linear_search(&arr, target) {
        -1 => println!("Target {} not found", target),
        idx => println!("Target {} found at index {}", target, idx),
    }
}

Line-by-line explanation

fn linear_search(arr: &[i32], target: i32) -> i32 Takes a borrowed slice of i32 values and the target value. Returns i32 — negative one is used as the sentinel for "not found," following the C convention. An idiomatic Rust alternative would return Option<usize>, but i32 keeps this comparable to other languages.

for i in 0..arr.len() Iterates from index 0 through the last valid index (arr.len() - 1). The range 0..n is exclusive on the right, so no off-by-one risk.

if arr[i] == target The equality check. Rust panics on out-of-bounds access, so this is safe — i is always within 0..arr.len().

return i as i32 arr.len() returns usize (an unsigned type). Casting to i32 allows us to return -1 from the same function. In a real codebase, Option<usize> avoids the cast.

-1 The implicit return (no semicolon) when the loop completes without a match. Signals "not found."

Two checks per iteration

Notice that every loop iteration performs two checks:

1. i < arr.len() — the bounds check embedded in the range (the loop termination condition).
2. arr[i] == target — the equality check.

For an array of n elements where the target is absent, that is 2n comparisons total. The sentinel optimization below reduces this to n + 1.

Optimized Implementation: Sentinel Search

The bound check i < n exists to prevent reading past the end of the array. But what if you guaranteed that the target would always be found before the end? Then the bound check is redundant — the equality check is enough to stop the loop.

The idea: temporarily append the target to the end of the array before searching. Now the loop only needs one condition: arr[i] == target. In the worst case (target not in original data), the loop stops at the appended sentinel. After the loop, check whether i points to a real position or the sentinel.

This halves the number of comparisons in the inner loop from 2 to 1.

fn linear_search_sentinel(arr: &mut Vec<i32>, target: i32) -> i32 {
    let n = arr.len();            // save original length before appending
    arr.push(target);             // append target as sentinel at index n
 
    let mut i = 0;
    while arr[i] != target {      // only ONE check per iteration (no bounds check)
        i += 1;
    }
 
    arr.pop();                    // restore the array to its original state
 
    if i < n {                    // did we stop before the sentinel?
        i as i32                  // yes: found in the original array
    } else {
        -1                        // no: only the sentinel matched
    }
}
 
fn main() {
    let mut arr = vec![64, 25, 12, 22, 11];
 
    println!("{}", linear_search_sentinel(&mut arr, 22));  // 3
    println!("{}", linear_search_sentinel(&mut arr, 99));  // -1
 
    // arr is back to [64, 25, 12, 22, 11] after each call
    println!("{:?}", arr);
}

What changed and why

Before (naive): for i in 0..arr.len() checks i < n on every iteration — that is the loop termination condition the compiler emits. Inside the body, arr[i] == target is checked. Two operations per element.

After (sentinel): while arr[i] != target is the only check. There is no bound test. The loop will stop because we guaranteed target exists somewhere in the extended array. One operation per element.

The trade: you need mutable access to the array (to push and pop) and must restore it afterward. In a single-threaded context this is fine. In concurrent code, mutating shared data is unsafe — sentinel search would need a separate working buffer.

arr.push(target) / arr.pop() Rust's Vec<i32> is a heap-allocated growable array. push appends in amortized O(1) time; pop removes the last element in O(1). The array is logically restored to its original state.

if i < n After the loop, i is either an index within [0, n-1] (target found in original data) or exactly n (only the sentinel matched). This check distinguishes the two cases.

A note on Rust idioms

In practice, Rust's standard library provides slice::iter().position():

fn linear_search_idiomatic(arr: &[i32], target: i32) -> Option<usize> {
    arr.iter().position(|&x| x == target)
}

This returns Some(index) on success and None on failure — no sentinel needed, no mutation, no i32 cast. The sentinel version is shown here as a concrete optimization technique, not as the preferred Rust style.

Time Complexity

Best Case — O(1)

The target is the first element.

arr = [22, 25, 12, 64, 11], target = 22

Step 1: arr[0] = 22 == 22 → return 0

One comparison, done. The loop body executes exactly once regardless of array size. This is O(1).

When does this happen? When the target is at index 0. For random data with the target present at a uniformly random position, it happens with probability 1/n.

Average Case — O(n)

Assume the target is present and equally likely to be at any position. The expected number of comparisons is:

E[comparisons] = (1 + 2 + 3 + ... + n) / n
               = n(n + 1) / 2 / n
               = (n + 1) / 2

For large n, this is approximately n/2. Since Big-O drops constants: O(n).

If the target is absent with probability p and present with probability (1-p), the expected comparisons are:

E = p × n + (1-p) × (n+1)/2

For p = 1/2 (target absent half the time), E ≈ 3n/4 — still O(n).

Worst Case — O(n)

The target is either at the last index or absent entirely.

arr = [64, 25, 12, 22, 11], target = 11  → checks all 5 elements
arr = [64, 25, 12, 22, 11], target = 99  → checks all 5 elements, returns -1

Both require n comparisons. This is the upper bound — no input can force more than n comparisons. Therefore: O(n).

Summary table

The best and average cases are technically Ω(1) and Θ(n/2), but we report the worst case O(n) when characterizing the algorithm.

Space Complexity

Naive implementation — O(1)

The naive implementation uses exactly three variables:

• i — the loop counter (one word of stack space)
• The function parameters arr (a fat pointer: address + length, two words) and target (one word)

None of these scale with the input size. No heap allocation, no recursion, no data structures. Space: O(1).

Sentinel implementation — O(1) amortized

arr.push(target) may trigger a Vec reallocation if the current capacity is exhausted. In the worst case this allocates a new buffer of 2n elements, copying all n existing elements — O(n) time and O(n) space for that one push. However:

• If arr has spare capacity (which it usually does after Vec::with_capacity or after earlier pushes), push is O(1) with no allocation.
• The pop at the end removes the sentinel without releasing memory.

For space complexity, we care about extra memory required, not capacity. The single appended element is O(1) extra space. Reallocation, when it occurs, is an implementation detail of Vec — the logical extra space is still one element.

Iterative vs recursive

Linear search is naturally iterative. A recursive version would look like:

fn linear_search_recursive(arr: &[i32], target: i32, i: usize) -> i32 {
    if i >= arr.len() {
        return -1;
    }
    if arr[i] == target {
        return i as i32;
    }
    linear_search_recursive(arr, target, i + 1)
}

Each recursive call pushes a new stack frame containing arr (fat pointer), target, and i. For an array of n elements where the target is absent, the recursion depth is n. Stack space: O(n).

This is a concrete reason to prefer the iterative form: identical logic at O(1) stack space instead of O(n). For large arrays, the recursive version risks a stack overflow. Rust's default stack size is typically 8 MB; at ~64 bytes per frame, that is roughly 100,000 frames before overflow.

When to Use Linear Search

Linear search is the right choice when:

• Data is unsorted — binary search requires sorted input. If you cannot sort (or the cost of sorting exceeds the savings), linear search is your only option.
• Search happens rarely — if you search once and the array has 100 elements, the overhead of sorting is not worth it.
• Data changes frequently — maintaining a sorted structure (or a hash map) has upfront cost. For append-heavy workloads with infrequent searches, unsorted + linear search may win.
• The array is tiny — for n < ~16, cache effects make linear search competitive with or faster than binary search, because the entire array fits in a cache line.

Binary search requires O(n log n) to sort first, then O(log n) per query. Linear search pays O(n) per query but O(0) to prepare. The breakeven point: if you run k queries, sort when k × O(n) > O(n log n), i.e., k > log n.