Data Structures & Algorithms - Linear Search Algorithm

Share with a Friend

Linear Search Algorithm

Linear Search is the simplest searching algorithm. It sequentially checks each element of the list/array until a match is found or the whole list has been searched.

How it works?

• Start from the first element.
• Compare the current element with the target value.
• If it matches, return the index.
• Otherwise, move to the next element.
• Repeat until the target is found or the end of the list is reached.

Time Complexity

• Best case: O(1) — when the target is at the first element.
• Worst case: O(n) — when the target is at the last element or not present.
• Average case: O(n)

Space Complexity

• O(1) — Linear search uses constant extra space.

Pseudocode

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

Detailed Explanation & Example: Linear Search

Algorithm:

1. Start from the first element.
2. Compare each element with the target.
3. If match found, return index.
4. If no match found, return -1.

Linear Search implementation - C, C++, Java, Python

#include <stdio.h>
 
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}
 
int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr)/sizeof(arr[0]);
    int target = 30;
    int result = linearSearch(arr, n, target);
    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found\n");
    return 0;
}

Element found at index 2

#include <iostream>
using namespace std;
 
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}
 
int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr)/sizeof(arr[0]);
    int target = 30;
    int result = linearSearch(arr, n, target);
    if (result != -1)
        cout << "Element found at index " << result << endl;
    else
        cout << "Element not found" << endl;
    return 0;
}

Element found at index 2

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 = {10, 20, 30, 40, 50};
        int target = 30;
        int result = linearSearch(arr, target);
        if (result != -1)
            System.out.println("Element found at index " + result);
        else
            System.out.println("Element not found");
    }
}
 

Element found at index 2

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1
 
arr = [10, 20, 30, 40, 50]
target = 30
result = linear_search(arr, target)
if result != -1:
    print(f"Element found at index {result}")
else:
    print("Element not found")

Element found at index 2

Real-World Applications of Linear Search

• Finding a specific value in a small or unsorted list.
• Searching in data structures that do not support random access (e.g., linked lists).
• Simple text search in documents.
• Useful when data size is small or searching infrequently.