Linear Search

Overview

Linear search, also known as sequential search, is the simplest searching algorithm. It sequentially checks each element in a list until it finds the target value or reaches the end of the list.

Despite its simplicity, linear search is fundamental and widely used, especially when data is unsorted or when working with small datasets where the overhead of more complex algorithms isn't justified.

How It Works

The algorithm works by:

  1. Starting from the first element of the array
  2. Comparing each element with the target value
  3. If a match is found, returning the index
  4. If the end is reached without finding a match, returning -1 (or indicating not found)

Algorithm


LinearSearch(arr, target):
    for i = 0 to arr.length - 1:
        if arr[i] == target:
            return i
    return -1  # Target not found

Implementation


def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

Complexity Analysis

  • Time Complexity:
    • Best Case: O(1) - Target found at the first position
    • Average Case: O(n) — about n/2 comparisons when the target is present and equally likely to be anywhere, and n when it is absent. Note that O(n/2) and O(n) are the same set, so the correct relation is "=", not "≈" — constant factors vanish inside big-O.
    • Worst Case: O(n) - Target not found or at the last position
  • Space Complexity: O(1) - Only using a constant amount of extra space

Characteristics

  • Simple: Easy to understand and implement
  • No Prerequisites: Works on any data structure (arrays, lists, etc.)
  • No Sorting Required: Works on unsorted data
  • Inefficient for Large Data: Must check every element in worst case

One practical note that cuts against the theory: for small arrays linear search often beats binary search despite the worse complexity. It reads memory sequentially, which the cache and prefetcher handle perfectly, and it has no unpredictable branches; binary search jumps around and mispredicts on nearly every comparison. The crossover is typically somewhere around 32–128 elements depending on element size. This is the same reason production sorts fall back to insertion sort on small subarrays.

When to Use Linear Search

Linear search is appropriate when:

  • Data is unsorted and sorting would be more expensive than searching
  • Working with small datasets where O(n) is acceptable
  • Data is frequently changing, making it impractical to maintain sorted order
  • Simplicity is more important than performance
  • Searching through linked lists or other sequential data structures

Example

Searching for 7 in [3, 1, 7, 9, 2, 5]: 

Step 1: Check arr[0] = 3, not equal to 7
Step 2: Check arr[1] = 1, not equal to 7
Step 3: Check arr[2] = 7, found! Return index 2

Related Algorithms

Explore other searching algorithms: