GoAlgo

GoAlgo

Linear Search

Search Algorithm

Linear Search

Linear Search is a simple searching algorithm that steps through an array one by one until it finds the target value or reaches the end.

No data to display.
Deep Dive

Understanding Linear Search in Detail

Linear Search, also known as Sequential Search, is the most fundamental searching algorithm in computer science. It works by examining each element in a list one by one until it finds a match or reaches the end of the list. While simple, this algorithm is the foundation for understanding more complex search techniques.

Imagine you lost your keys somewhere in your house. You might start at the front door and check every room, every drawer, and every pocket until you find them. You are essentially performing a linear search—systematically checking each location until you discover what you are looking for. This brute-force approach guarantees you will find the item if it exists.

The Logic Behind the Sequential Scan

The core mechanism of Linear Search is straightforward iteration.

  • Initialize: Start at the first element of the array (index 0).
  • Compare: Check if the current element matches the target value.
  • Found: If it matches, return the current index—search is complete!
  • Continue: If no match, move to the next element and repeat.
  • Not Found: If you reach the end of the array without a match, return -1 to indicate the target is not present.

Step-by-Step Algorithm Trace

Let's trace the algorithm searching for the value 22 in an unsorted array.

Input Array: [10, 23, 45, 70, 11, 22, 15]
Target: 22

Step 1: Check index 0

  • Compare arr[0] = 10 with target 22.
  • 10 ≠ 22 — Not a match.

Move to the next element.

Step 2: Check index 1

  • Compare arr[1] = 23 with target 22.
  • 23 ≠ 22 — Not a match.

Move to the next element.

Step 3: Check index 2

  • Compare arr[2] = 45 with target 22.
  • 45 ≠ 22 — Not a match.

Move to the next element.

Step 4: Check index 3

  • Compare arr[3] = 70 with target 22.
  • 70 ≠ 22 — Not a match.

Move to the next element.

Step 5: Check index 4

  • Compare arr[4] = 11 with target 22.
  • 11 ≠ 22 — Not a match.

Move to the next element.

Step 6: Check index 5

  • Compare arr[5] = 22 with target 22.
  • 22 = 22 — Match found!

Target found at index 5. Return 5.

Code Implementation

Below is the implementation of Linear Search in multiple programming languages. The algorithm is simple yet effective for small or unsorted datasets.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target)
            return i;  // Element found at index i
    }
    return -1;  // Element not found
}
int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
    
    int result = linearSearch(arr, n, target);
    
    if (result == -1)
        printf("Element not found");
    else
        printf("Element found at index %d", result);
    
    return 0;
}
C • 24 lines.c

Time & Space Complexity Analysis

Understanding the efficiency of Linear Search helps us appreciate when to use it and when to choose faster alternatives.

Time Complexity

O(n)Worst Case

This occurs when the target element is at the very end of the array or does not exist at all. The algorithm must check every single element before concluding.

O(n)Average Case

On average, the target will be found somewhere in the middle of the array, requiring roughly n/2 comparisons. In Big-O notation, this simplifies to O(n).

O(1)Best Case

This happens when the target element is the very first element in the array. Only one comparison is needed to find it.

Space Complexity

O(1)Constant Space

Linear Search uses only a few variables (like loop counters and the target value) regardless of input size. It does not require any additional data structures.

When to Use Linear Search?

While Linear Search may seem inefficient compared to Binary Search, it has several important advantages that make it the right choice in many scenarios.

Unsorted Data

Linear Search works on any data without requiring it to be sorted first. If your data changes frequently and maintaining sorted order is expensive, Linear Search is often the practical choice.

Small Datasets

For small arrays (typically fewer than 100 elements), the simplicity and low overhead of Linear Search often outperforms more complex algorithms that have higher setup costs.

Linked Lists

Unlike arrays, linked lists do not support random access, making Binary Search impossible. Linear Search is the only option for searching through linked data structures.