Linear Search: Sequential Search Algorithm

Key Insights

Linear search is the most versatile search algorithm—it works on any data structure, sorted or unsorted, and requires no preprocessing, making it the pragmatic choice for small datasets and complex search criteria.
The O(n) time complexity sounds inefficient, but for datasets under ~100 elements, linear search often outperforms binary search due to lower overhead and better cache locality.
Optimizations like sentinel search and move-to-front heuristics can significantly improve real-world performance when the same elements are searched repeatedly.

Introduction to Linear Search

Linear search, also called sequential search, is the most fundamental searching algorithm in computer science. You start at the beginning of a collection and check each element one by one until you find what you’re looking for or run out of elements to check.

It’s the algorithm equivalent of looking for your keys by checking every pocket in order. Not glamorous, but it works every time.

While computer science education often rushes past linear search to get to “more interesting” algorithms like binary search, this dismissiveness is misguided. Linear search remains the workhorse algorithm in production code for good reasons: it’s simple to implement correctly, works on any data structure, and often outperforms fancier alternatives in real-world scenarios.

How Linear Search Works

The algorithm is straightforward:

Start at the first element
Compare the current element with the target
If they match, return the position
If not, move to the next element
Repeat until you find the target or exhaust all elements

Here’s the basic implementation:

def linear_search(arr, target):
    """
    Search for target in arr, return index if found, -1 otherwise.
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Usage
numbers = [64, 34, 25, 12, 22, 11, 90]
result = linear_search(numbers, 22)
print(f"Element found at index: {result}")  # Output: 4

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}

// Usage
const numbers = [64, 34, 25, 12, 22, 11, 90];
const result = linearSearch(numbers, 22);
console.log(`Element found at index: ${result}`); // Output: 4

The logic is identical across languages. This simplicity is a feature, not a bug—there’s almost nothing that can go wrong.

Implementation Variations

Real-world requirements rarely match the textbook “find first occurrence” scenario. Here are practical variations you’ll actually use.

Finding All Occurrences

def find_all_indices(arr, target):
    """Return all indices where target appears."""
    indices = []
    for i, element in enumerate(arr):
        if element == target:
            indices.append(i)
    return indices

# Usage
data = [1, 3, 5, 3, 7, 3, 9]
print(find_all_indices(data, 3))  # Output: [1, 3, 5]

Finding Last Occurrence

def find_last(arr, target):
    """Return index of last occurrence, -1 if not found."""
    last_index = -1
    for i, element in enumerate(arr):
        if element == target:
            last_index = i
    return last_index

# Or search backwards for efficiency
def find_last_optimized(arr, target):
    for i in range(len(arr) - 1, -1, -1):
        if arr[i] == target:
            return i
    return -1

Searching in Linked Lists

Linear search is the only option for linked lists since you can’t jump to arbitrary positions:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def search_linked_list(head, target):
    """Search linked list, return node if found, None otherwise."""
    current = head
    position = 0
    
    while current is not None:
        if current.data == target:
            return position
        current = current.next
        position += 1
    
    return -1

# Build a simple list
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)

print(search_linked_list(head, 20))  # Output: 1

Time and Space Complexity Analysis

Linear search has predictable complexity characteristics:

Case	Time Complexity	When It Occurs
Best	O(1)	Target is first element
Average	O(n/2) → O(n)	Target is in middle
Worst	O(n)	Target is last or absent

Space Complexity: O(1)—you only need a loop counter regardless of input size.

Here’s how linear search compares to alternatives:

Algorithm	Time (Average)	Space	Requires Sorted?	Works on Linked Lists?
Linear Search	O(n)	O(1)	No	Yes
Binary Search	O(log n)	O(1)	Yes	No
Hash Table	O(1)	O(n)	No	N/A
Jump Search	O(√n)	O(1)	Yes	No

The table reveals linear search’s advantage: it’s the only algorithm that works everywhere with no prerequisites.

When to Use Linear Search

Stop reaching for binary search by default. Linear search is the better choice in these scenarios:

Unsorted Data

If your data isn’t sorted and you only need one search, linear search wins. Sorting first (O(n log n)) plus binary search (O(log n)) is slower than a single linear search (O(n)).

Small Datasets

For arrays under ~100 elements, linear search often beats binary search due to simpler operations and better branch prediction. The overhead of binary search’s index calculations isn’t worth it.

Complex Search Criteria

When searching by computed properties or multiple conditions, linear search with a predicate function is cleaner:

def find_by_predicate(arr, predicate):
    """Find first element matching the predicate function."""
    for i, element in enumerate(arr):
        if predicate(element):
            return i, element
    return -1, None

# Search objects by property
users = [
    {"id": 1, "name": "Alice", "active": False},
    {"id": 2, "name": "Bob", "active": True},
    {"id": 3, "name": "Charlie", "active": True},
]

# Find first active user
index, user = find_by_predicate(users, lambda u: u["active"])
print(f"First active user: {user['name']}")  # Output: Bob

# Find user by complex criteria
index, user = find_by_predicate(
    users, 
    lambda u: u["active"] and u["name"].startswith("C")
)
print(f"Active user starting with C: {user['name']}")  # Output: Charlie

Streaming Data

When processing data streams where you can’t store everything in memory, linear search is your only option:

def search_stream(stream, target):
    """Search through an iterator/generator."""
    for i, element in enumerate(stream):
        if element == target:
            return i
    return -1

Optimizations and Variants

When linear search is the right tool, these optimizations can improve performance.

Sentinel Linear Search

Eliminate the bounds check on every iteration by placing the target at the end:

def sentinel_search(arr, target):
    """
    Sentinel search eliminates one comparison per iteration.
    Note: Modifies array temporarily.
    """
    n = len(arr)
    if n == 0:
        return -1
    
    # Save last element and place sentinel
    last = arr[n - 1]
    arr[n - 1] = target
    
    i = 0
    while arr[i] != target:
        i += 1
    
    # Restore last element
    arr[n - 1] = last
    
    # Check if we found target or hit sentinel
    if i < n - 1 or arr[n - 1] == target:
        return i
    return -1

This removes one comparison per iteration—the i < n check. For large arrays with many searches, this adds up.

Move-to-Front Heuristic

When the same elements are searched repeatedly, move found elements to the front:

def search_with_mtf(arr, target):
    """
    Move-to-front: recently accessed elements bubble to the front.
    Good when access patterns have temporal locality.
    """
    for i, element in enumerate(arr):
        if element == target:
            if i > 0:
                # Move to front
                arr.pop(i)
                arr.insert(0, element)
            return 0  # Now at front
    return -1

This is particularly effective for caches and recently-used lists.

Linear Search vs. Binary Search

The choice between linear and binary search isn’t always obvious. Here’s a practical benchmark:

import time
import random

def benchmark_searches(sizes):
    """Compare linear and binary search across different array sizes."""
    
    def linear_search(arr, target):
        for i, val in enumerate(arr):
            if val == target:
                return i
        return -1
    
    def binary_search(arr, target):
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == target:
                return mid
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1
    
    print(f"{'Size':<10} {'Linear (μs)':<15} {'Binary (μs)':<15} {'Winner'}")
    print("-" * 50)
    
    for size in sizes:
        arr = sorted(random.sample(range(size * 10), size))
        target = arr[size // 2]  # Search for middle element
        
        # Benchmark linear
        start = time.perf_counter()
        for _ in range(1000):
            linear_search(arr, target)
        linear_time = (time.perf_counter() - start) * 1000  # ms for 1000 runs
        
        # Benchmark binary
        start = time.perf_counter()
        for _ in range(1000):
            binary_search(arr, target)
        binary_time = (time.perf_counter() - start) * 1000
        
        winner = "Linear" if linear_time < binary_time else "Binary"
        print(f"{size:<10} {linear_time:<15.2f} {binary_time:<15.2f} {winner}")

benchmark_searches([10, 50, 100, 500, 1000, 10000])

Typical results show linear search winning for arrays under 50-100 elements, with binary search pulling ahead as sizes grow.

Decision Framework:

Use linear search when: data is unsorted, dataset is small (<100 elements), you’re searching once, you need complex predicates, or you’re working with linked lists.
Use binary search when: data is sorted, dataset is large, you’re searching repeatedly, and you can afford the sorted-array constraint.

Linear search isn’t a fallback—it’s a deliberate choice. Know when simplicity wins.