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.

How It Works

Start at the first element of the list.
Compare the current element with the target value.
If they match, return the index or position and stop.
If they do not match, move to the next element.
Repeat steps 2-4 until a match is found.
If the list ends without a match, return -1 or a failure signal.

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.

Implementation#

#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
}

def linear_search(array: list[int], /, *, target: int) -> int:
  for index, value in enumerate(array):
    if value == target:
      return index
  return -1


array: list[int] = [ 1, 2, 3 ]
linear_search(array, target = 2) # index 1
linear_search(array, target = 5) # -1; target not found