Mastering Algorithms

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/2) ≈ O(n) - Target found in the middle on average
    • 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

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: