Linear search algorithm | Linear search program in C, Example

The linear search algorithm is a very simple and straightforward in data structure. A linear search is also known as a sequential search. If the list or array is unordered, the linear search is preferable.

Linear search is an excellent approach to find elements, however we must check each element of the array or list in this search. As a result, the program’s speed slows down in comparison to others.

How does linear search work?

The search begins sequentially, with the leading element being compared to the entries in the list. We check each item in the list and return a flag if a match is found; otherwise, we keep searching until we reach the end of the list or array.

Linear search algorithm Steps

We can cover the full searching with only 6 steps since the steps of the sequential search are so simple.

• Step 1: Take the first element from the list which will be the current element.
• Step 2: Make a comparison between the current element and the key element. If both are same, go to step 5.
• Step 3: If the next element is present in the list, consider it as the current element and got to Step 2.
• Step 4: If key element not found in list. Go to step 6.
• Step 5: Key element found then return location or flag.
• Step 6: Exit of the Algorithm.

Pseudocode of Linear search algorithm

search (array, key)
   for item in the array
      if match item == key then
         return the flag;
      end if
   end for
end of search

Linear search program in C using array

#include <stdio.h>
#define MAX 7

int lrSearch(int arr[], int keyElement) {
  int i = 0;
  for (i = 0; i < MAX; i++) {
    if (arr[i] == keyElement) {
      return i;
    }
  }
  return -1;
}
int main() {
  int arr[] = {
    11,
    21,
    31,
    41,
    51,
    61,
    71
  };
  int keyElement = 31;
  printf("Position of element %d is %d\n", keyElement, (lrSearch(arr, keyElement) + 1));
  return 0;
}

Output:
Position of element 31 is 3

Different program of Linear search in C

#include <stdio.h>

#define MAX 7
void linear_search(int list[], int keyElement) {
  int i, flag = 0;
  for (i = 0; i < MAX; i++)
    if (list[i] == keyElement) {
      printf("\nThe element %d is present at position %d in list\n", keyElement, i);
      flag = 1;
      break;
    }
  if (flag == 0) {
    printf("\nThe element %d is not present in the list\n", keyElement);
  }
}

void printlist(int list[]) {
  int i;
  printf("The elements of the list are: \n");
  for (i = 0; i < MAX; i++) {
    printf("%d\t", list[i]);
  }
}
void main() {
  int list[MAX] = {
    10,
    11,
    12,
    13,
    15,
    16,
    17
  }, n, keyElement = 16;

  printf("\nThe list before sorting is:\n");
  printlist(list);
  linear_search(list, keyElement);
}

Output:
The list before sorting is:
The elements of the list are: 
10      11      12      13      15      16      17
The element 16 is present at position 5 in list

Linear search algorithm Time Complexity

Because the search time is proportional to the number of comparisons required, this will typically do about n/2 comparisons.

• Worst Case Complexity of Linear Search is O(n).
• Average Case Complexity of Linear Search is O(n).
• Best Case Complexity of Linear Search is O(1).

Linear search algorithm Space Complexity

Space Complexity of Linear Search is O(1).

In conclusion, When the number of entries in the list is small, we should use the linear (sequential) search approach.