Linear Search

A linear search (also known as a sequential search) is a simple searching algorithm that checks every element in a data collection one by one in a sequential order until it finds the target value or reaches the end of the collection.

Key Characteristics

No Sorting Required

Unlike a binary search, it works perfectly on unsorted data collections.

Data Independent

It accommodates both numeric and non-numeric objects like strings.

Inefficient for Scale

The processing time grows linearly with the size of the data structure, making it impractical for massive databases.

Time and Space Complexity

The performance of a linear search scales proportionally with the number of elements \(n\) in the dataset.

Best-Case Time Complexity: \(O(1)\)

The target element is located at the very first position.

Worst-Case Time Complexity: \(O(n)\)

The target element is at the end of the list or does not exist at all.

Average Time Complexity: \(O(n)\)

The target element is found somewhere in the middle.

Space complexity**: \(O(1)\)

It operates directly on the existing list without requiring extra memory allocation.

How It Works

1. Start at the first element of the list.

2. Compare the current element with the target value.

3. If they match, return the index or position and stop.

4. If they do not match, move to the next element.

5. Repeat steps 2-4 until a match is found.

6. If the list ends without a match, return -1 or a failure signal.

Visualization

Source: GeeksforGeeks

Implementation

C++Python

#include <iostream>

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

int main() {
  int array[3] = { 1, 2, 3 };
  linearSearch(array, 2); // index 1
  linearSearch(array, 5); // -1; target not found
}