Offensive Security Researcher & Quantum Cryptography Analyst

Linear Search Algorithm: Working, Explanation, and Simple Search Method

Abdul Wahab Junaid
linear search algorithm and working of this algorithm

linear search algorithm and working of this algorithm

I always start explaining search algorithms with linear search, because it is the most direct, no-assumptions way I can look for something: I check each element one by one, in order, until I either find what I am looking for or run out of elements to check. It requires no preconditions about the data — unlike binary search, it works equally well on sorted or unsorted collections — and its simplicity makes it the natural baseline against which every other search algorithm gets compared. While it is not the fastest option for large datasets, I still reach for it constantly in small collections or one-off searches where the overhead of sorting or building a more complex structure simply isn’t worth it.

History and Background

Linear search does not have a formal “invention” the way more sophisticated algorithms do, since it reflects the most basic and intuitive method of searching — checking items one at a time — that predates computer science entirely, going back to how humans have always searched through physical collections of items. As one of the earliest algorithms formally described in computing literature, it appears in foundational texts from the 1950s and 60s as the natural starting point before more advanced searching techniques like binary search were introduced. It remains foundational in algorithm education specifically because its simplicity provides a clear baseline for teaching Big O notation and time complexity analysis.

Problem Statement

I need a method to determine whether a specific value exists within a collection, and if so, to find its position, without requiring any particular ordering of the data beforehand. Linear search solves this in the most direct way possible: examining each element sequentially until a match is found or the entire collection has been checked, making it applicable to any data structure that supports sequential access, regardless of whether it is sorted.

Core Concepts

How It Works

I carry out linear search through these steps:

  1. I start at the first element of the collection.
  2. I compare the current element with the target value.
  3. If they match, I return the current index (or a “found” indicator) immediately.
  4. If they don’t match, I move to the next element and repeat the comparison.
  5. If I reach the end of the collection without finding a match, I conclude the target is not present and return an appropriate “not found” indicator.

Working Principle

The mechanism behind linear search is about as direct as an algorithm can get — there is no cleverness in eliminating candidates or narrowing a search space, only a straightforward, exhaustive comparison against every element in sequence. This directness is exactly why it works on any dataset, sorted or not, and on any data structure that permits sequential traversal, even those without random access like singly linked lists. The trade-off I always weigh is that this generality comes at the cost of efficiency: without any structural assumption to exploit, the algorithm has no way to skip over unpromising sections of the data.

Mathematical Foundation

For a collection of size n, if the target is present, the number of comparisons needed depends on its position. If the target is equally likely to be at any position (a uniform distribution assumption), the expected number of comparisons is:

$$E[\text{comparisons}] = \frac{1}{n}\sum_{i=1}^{n} i = \frac{n+1}{2}$$

giving an average-case time complexity of:

$$T_{avg}(n) = O(n)$$

In the worst case — where the target is the last element checked, or absent entirely — the algorithm performs exactly n comparisons:

$$T_{worst}(n) = O(n)$$

In the best case, where the target is the very first element:

$$T_{best}(n) = O(1)$$

Diagrams

flowchart TD
    A[Start: i = 0] --> B{i < length of array?}
    B -->|No| C[Target not found, return -1]
    B -->|Yes| D{A of i equals target?}
    D -->|Yes| E[Return index i]
    D -->|No| F[i = i + 1]
    F --> B
graph LR
    A["[5,3,8,2,9,1] target=9"] -->|"check 5, no match"| B["check 3, no match"]
    B -->|"check 8, no match"| C["check 2, no match"]
    C -->|"check 9, match!"| D["return index 4"]

Pseudocode

LINEAR-SEARCH(A, target)
    n = length(A)
    for i = 0 to n - 1
        if A[i] == target
            return i
    return -1  // target not found

Step-by-Step Example

I will search for the target value 9 in the array [5, 3, 8, 2, 9, 1].

Step 1: i=0. A[0] = 5. 5 ≠ 9, move on.

Step 2: i=1. A[1] = 3. 3 ≠ 9, move on.

Step 3: i=2. A[2] = 8. 8 ≠ 9, move on.

Step 4: i=3. A[3] = 2. 2 ≠ 9, move on.

Step 5: i=4. A[4] = 9. Match found! Return index 4.

Result: Target 9 found at index 4, after 5 comparisons.

If I instead searched for a value not present, such as 100, the algorithm would check all 6 elements before returning -1.

Time Complexity

Space Complexity

Linear search requires only O(1) additional space, since it just needs a single index variable to track its current position during the scan. It needs no auxiliary data structures of any kind, making it as memory-efficient as an algorithm can be.

Correctness Analysis

I prove linear search’s correctness using a simple loop invariant: at the start of each iteration, the target has not been found in any of the previously checked positions A[0..i-1]. This holds trivially at the start, since no positions have been checked yet. During each iteration, I check A[i]: if it matches the target, I immediately return the correct index, which is provably correct since I have exhaustively confirmed no earlier position matched. If it does not match, the invariant extends to A[0..i], and I proceed to the next index. If the loop completes without finding a match, the invariant guarantees that every position in the array has been checked and found not to match, which correctly justifies returning “not found.”

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>

// Linear search implementation
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;  // target found at index i
        }
    }
    return -1;  // target not found
}

int main() {
    int arr[] = {5, 3, 8, 2, 9, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 9;

    int result = linearSearch(arr, n, target);

    if (result != -1) {
        printf("Target %d found at index %d\n", target, result);
    } else {
        printf("Target %d not found in array\n", target);
    }

    return 0;
}

Sample Input and Output

Input: Array [5, 3, 8, 2, 9, 1], target = 9

Output: Target 9 found at index 4

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version