What is Linear Search in Data Structures — Its Algorithm, Working, & Complexity

Linear Search (also known as Sequential Search) is the simplest searching algorithm. It works by sequentially checking each element in a data structure until the target is found or the end of the structure is reached. It does not require the data to be sorted and can be applied to arrays, linked lists, and other linear data structures.

Algorithm Steps

1. Start from the first element of the data structure.
2. Compare the current element with the target value.
3. If the current element equals the target, return the index/position.
4. If not, move to the next element and repeat step 2.
5. If the end of the data structure is reached without finding the target, return -1 (or indicate "not found").

Pseudocode

function linear_search(array, target):
    for i from 0 to length(array) - 1:
        if array[i] == target:
            return i
    return -1

Step-by-Step Working Example

Let's trace linear search on the array [5, 2, 8, 1, 9, 4] searching for the target 9:

• Step 1: Check index 0: arr[0] = 5 → not a match.
• Step 2: Check index 1: arr[1] = 2 → not a match.
• Step 3: Check index 2: arr[2] = 8 → not a match.
• Step 4: Check index 3: arr[3] = 1 → not a match.
• Step 5: Check index 4: arr[4] = 9 → Match found! Return index 4.

Implementation in Python

def linear_search(arr, target):
    """
    Perform linear search on the given array.
    Returns the index of target if found, otherwise -1.
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Example usage
arr = [5, 2, 8, 1, 9, 4]
target = 9
result = linear_search(arr, target)
if result != -1:
    print(f"Element found at index {result}")
else:
    print("Element not found")

Enhanced Linear Search with Early Exit

def linear_search_enhanced(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

Implementation in Java

public class LinearSearch {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9, 4};
        int target = 9;
        int result = linearSearch(arr, target);
        if (result != -1) {
            System.out.println("Element found at index " + result);
        } else {
            System.out.println("Element not found");
        }
    }
}

Generic Linear Search (Works with any type)

public class LinearSearchGeneric {
    public static  int linearSearch(T[] arr, T target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i].equals(target)) {
                return i;
            }
        }
        return -1;
    }
}

Implementation in C++

#include 
#include 
using namespace std;

int linearSearch(vector& arr, int target) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    vector arr = {5, 2, 8, 1, 9, 4};
    int target = 9;
    int result = linearSearch(arr, target);
    if (result != -1) {
        cout << "Element found at index " << result << endl;
    } else {
        cout << "Element not found" << endl;
    }
    return 0;
}

C++ Template Implementation (Generic)

#include 
using namespace std;

template 
int linearSearch(T arr[], int size, T target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

Complexity Analysis

Space Complexity

• Space: O(1) — uses only a few variables, no extra data structures.
• In-place: Yes, it modifies nothing in the original structure.

Advantages of Linear Search

• Simplicity: Easy to understand and implement.
• No Preprocessing: Does not require the data to be sorted.
• Works on Any Data Structure: Works on arrays, linked lists, and other linear structures.
• Small Data Sets: Perfectly fine for small datasets.
• Flexible: Can find the first occurrence, last occurrence, or count all occurrences.

Disadvantages of Linear Search

• Slow for Large Data: O(n) time is not efficient for large datasets.
• No Optimization: Cannot take advantage of any ordering in the data.
• Better Alternatives: Binary Search (O(log n)) is much faster for sorted data.

Variations of Linear Search

1. Find All Occurrences

def find_all_occurrences(arr, target):
    indices = []
    for i, val in enumerate(arr):
        if val == target:
            indices.append(i)
    return indices

# Example: [1, 3, 5, 3, 7, 3] → [1, 3, 5] for target=3

2. Find Last Occurrence

def find_last_occurrence(arr, target):
    last_index = -1
    for i, val in enumerate(arr):
        if val == target:
            last_index = i
    return last_index

3. Search from Both Ends (Optimized)

def linear_search_both_ends(arr, target):
    left = 0
    right = len(arr) - 1
    while left <= right:
        if arr[left] == target:
            return left
        if arr[right] == target:
            return right
        left += 1
        right -= 1
    return -1

4. Sentinel Linear Search

Adds a sentinel at the end to avoid checking the boundary condition in each iteration.

def sentinel_linear_search(arr, target):
    n = len(arr)
    last = arr[-1]
    arr[-1] = target  # Place sentinel at the end
    i = 0
    while arr[i] != target:
        i += 1
    arr[-1] = last  # Restore original value
    if i < n - 1 or last == target:
        return i
    return -1

Linear Search vs Binary Search

Applications

• Small Datasets: When n is small, linear search is simple and efficient enough.
• Unsorted Data: When the data cannot be sorted or sorting is not practical.
• Linked Lists: Since linked lists don't support random access, linear search is the only option.
• Finding Multiple Occurrences: Can easily find all occurrences of a target.
• Real-time Systems: When latency is critical and data is small.
• Searching in Databases: Used in simple query operations on small tables.

Key Takeaways

• Linear search is the simplest searching algorithm.
• It checks elements sequentially from the first to the last.
• Time complexity: O(n) in worst and average cases; O(1) in best case.
• Does not require sorted data — works on any linear data structure.
• Use linear search for small datasets, unsorted data, or linked lists.
• For large, sorted datasets, binary search is significantly faster.