Linear Search

Linear search is a very basic and simple search algorithm. In Linear search, we search an element or value in a given array by traversing the array from the starting, till the desired element or value is found.

Implementing Linear Search

Following are the steps of implementation that we will be following:

1. Traverse the array using a for loop.
2. In every iteration, compare the target value with the current value of the array.
   • If the values match, return the current index of the array.
   • If the values do not match, move on to the next array element.
3. If no match is found, return -1.

To search the number 1 in the array given below, linear search will go step by step in a sequential order starting from the first element in the given array.

Start from the first element, compare k with each element x.

If x == k, return the index.

Else, return not found.

Linear Search Algorithm

LinearSearch(array, key)
  for each item in the array
    if item == value
      return its index

Linear Search Program in C

// Linear Search in C

#include <stdio.h>

int search(int array[], int n, int x) {
  
  // Going through array sequencially
  for (int i = 0; i < n; i++)
    if (array[i] == x)
      return i;
  return -1;
}

int main() {
  int array[] = {2, 4, 0, 1, 9};
  int x = 1;
  int n = sizeof(array) / sizeof(array[0]);

  int result = search(array, n, x);

  (result == -1) ? printf("Element not found") : printf("Element found at index: %d", result);
}

Linear Search Complexities

Time Complexity: O(n)

Space Complexity: O(1)

Linear Search Applications

1. For searching operations in smaller arrays (<100 items).