Linear Search Algorithm — Sequential Search Guide

What is Linear Search?

Linear search (also called sequential search) is the simplest and most straightforward searching algorithm. It works by checking each element of the array sequentially from the beginning to the end until the target element is found or the entire array has been traversed. Unlike binary search, linear search doesn't require the array to be sorted, making it versatile for any type of data structure.

The algorithm starts at the first element (index 0) and compares it with the target value. If they match, the search is successful and the index is returned. If not, it moves to the next element and repeats the process. This continues until either the target is found or all elements have been checked.

How Linear Search Works

Consider searching for the number 7 in the array: [5, 3, 8, 1, 9, 2, 7, 4, 6]

1. Step 1: Compare 5 with 7 → Not equal, move to next
2. Step 2: Compare 3 with 7 → Not equal, move to next
3. Step 3: Compare 8 with 7 → Not equal, move to next
4. Step 4: Compare 1 with 7 → Not equal, move to next
5. Step 5: Compare 9 with 7 → Not equal, move to next
6. Step 6: Compare 2 with 7 → Not equal, move to next
7. Step 7: Compare 7 with 7 → Match found! Return index 6

Characteristics of Linear Search

• Works on both sorted and unsorted arrays
• No preprocessing required (unlike binary search which needs sorting)
• Best for small datasets (typically less than 100 elements)
• Simple to implement - only requires a loop and comparison
• Works on any data structure that supports sequential access (arrays, linked lists)
• In-place algorithm - requires no extra memory

Time and Space Complexity

Where n is the number of elements in the array. In the worst case, we need to check all n elements, making it a linear time algorithm.

public class LinearSearch {

    // Iterative linear search - O(n) time, O(1) space
    static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;  // Found at index i
            }
        }
        return -1;  // Not found
    }

    // Recursive linear search - O(n) time, O(n) space (call stack)
    static int linearSearchRec(int[] arr, int index, int target) {
        // Base case 1: Reached end of array
        if (index == arr.length) {
            return -1;  // Not found
        }
        
        // Base case 2: Found the target
        if (arr[index] == target) {
            return index;
        }
        
        // Recursive case: Search in remaining array
        return linearSearchRec(arr, index + 1, target);
    }

    // Find ALL occurrences of target
    static void findAllOccurrences(int[] arr, int target) {
        boolean found = false;
        System.out.print("Indices where " + target + " is found: ");
        
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                System.out.print(i + " ");
                found = true;
            }
        }
        
        if (!found) {
            System.out.print("Not found");
        }
        System.out.println();
    }

    // Linear search with custom comparator (for objects)
    static  int linearSearchGeneric(T[] arr, T target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i].equals(target)) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 1, 9, 2, 7, 4, 6};
        
        // Test iterative search
        System.out.println("Array: [5, 3, 8, 1, 9, 2, 7, 4, 6]");
        System.out.println("Search 7: index " + linearSearch(arr, 7));    // 6
        System.out.println("Search 10: index " + linearSearch(arr, 10));  // -1
        
        // Test recursive search
        System.out.println("Recursive search 9: index " + 
            linearSearchRec(arr, 0, 9));  // 4
        
        // Test find all occurrences
        int[] arr2 = {3, 1, 4, 1, 5, 9, 2, 6, 1};
        System.out.println("\nArray: [3, 1, 4, 1, 5, 9, 2, 6, 1]");
        findAllOccurrences(arr2, 1);  // Indices: 1 3 8
        
        // Test with strings
        String[] names = {"Alice", "Bob", "Charlie", "David"};
        System.out.println("\nSearch 'Charlie': index " + 
            linearSearchGeneric(names, "Charlie"));  // 2
    }
}

/*
 * Trace for arr = {5, 3, 8, 1, 9}, target = 9:
 * 
 * i=0: arr[0]=5 ≠ 9 → continue
 * i=1: arr[1]=3 ≠ 9 → continue
 * i=2: arr[2]=8 ≠ 9 → continue
 * i=3: arr[3]=1 ≠ 9 → continue
 * i=4: arr[4]=9 = 9 → return 4 ✓
 */

# Linear Search in Python

def linear_search(arr, target):
    """Iterative linear search - O(n) time, O(1) space"""
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Found at index i
    return -1  # Not found

def linear_search_recursive(arr, index, target):
    """Recursive linear search - O(n) time, O(n) space"""
    # Base case 1: Reached end of array
    if index == len(arr):
        return -1
    
    # Base case 2: Found the target
    if arr[index] == target:
        return index
    
    # Recursive case
    return linear_search_recursive(arr, index + 1, target)

def find_all_occurrences(arr, target):
    """Find all indices where target appears"""
    indices = [i for i, val in enumerate(arr) if val == target]
    return indices if indices else [-1]

# Test the functions
if __name__ == "__main__":
    arr = [5, 3, 8, 1, 9, 2, 7, 4, 6]
    
    print("Array:", arr)
    print("Search 7:", linear_search(arr, 7))        # 6
    print("Search 10:", linear_search(arr, 10))      # -1
    print("Recursive search 9:", linear_search_recursive(arr, 0, 9))  # 4
    
    arr2 = [3, 1, 4, 1, 5, 9, 2, 6, 1]
    print("\nArray:", arr2)
    print("All occurrences of 1:", find_all_occurrences(arr2, 1))  # [1, 3, 8]

#include <stdio.h>

// Iterative linear search - O(n) time, O(1) space
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;  // Found at index i
        }
    }
    return -1;  // Not found
}

// Recursive linear search - O(n) time, O(n) space
int linearSearchRec(int arr[], int index, int n, int target) {
    // Base case 1: Reached end of array
    if (index == n) {
        return -1;
    }
    
    // Base case 2: Found the target
    if (arr[index] == target) {
        return index;
    }
    
    // Recursive case
    return linearSearchRec(arr, index + 1, n, target);
}

int main() {
    int arr[] = {5, 3, 8, 1, 9, 2, 7, 4, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Array: [5, 3, 8, 1, 9, 2, 7, 4, 6]\n");
    printf("Search 7: index %d\n", linearSearch(arr, n, 7));    // 6
    printf("Search 10: index %d\n", linearSearch(arr, n, 10));  // -1
    printf("Recursive search 9: index %d\n", 
           linearSearchRec(arr, 0, n, 9));  // 4
    
    return 0;
}

Algorithm Steps

Advantages and Disadvantages

When to Use Linear Search

Practical Applications

• Searching in linked lists - Binary search doesn't work on linked lists
• Small datasets - Contact lists, shopping carts with few items
• Unsorted data - Recent search history, unsorted logs
• Finding all occurrences - Finding duplicate values in an array
• Database table scans - When no index is available
• File searching - Searching for a pattern in a text file

Linear Search vs Binary Search

Performance Comparison

For an array of size n = 1,000,000:

• Linear Search: Average ~500,000 comparisons, Worst ~1,000,000 comparisons
• Binary Search: Average ~20 comparisons, Worst ~20 comparisons

This shows why binary search is dramatically faster for large sorted datasets. However, if the array is unsorted, sorting it first takes O(n log n) time, which might make linear search more efficient for a single search operation.