In this tutorial, you will learn how the linear search algorithm works and its implementation using C.

Searching is the process of finding whether or not a specific value exists in an array. The linear search or sequential search works by checking every element of the array one by one until a match is found.

Working of Linear Search

Consider the following array. we have to search for an element X = 8 in the array using linear search.

Starting from the first element, compare X with each element in the list.

Return the index if item X is found, else return the element not found.

Linear Search Algorithm

1: SET POS = -1
2: SET I = 0
3: Repeat Step 4 while I <= N
4:   IF ARR[I] = VAL
‎       SET POS = I
‎       PRINT POS
‎       Go to Step 6
‎     [END OF IF]
‎     SET I = I + 1
‎   [END OF LOOP]
5: IF POS = –1
‎     PRINT "VALUE IS NOT PRESENT IN THE ARRAY"
‎   [END OF IF]
6: EXIT

C Example

The linear search algorithm can be implemented in C as follows:

//Linear search in C
‎
#include <stdio.h>
‎
int main()
{
‎  int arr[5] = {4, 1, 6, 8, 3};
‎  int x = 8, n = 5, pos = -1;
‎
‎  //compare x with each element in array 
‎  for (int i = 0; i < n; i++)
‎  {
‎    if (arr[i] == x)
‎    {
‎      //Print element found and exit
‎      pos = i;
‎      printf("Element found at position %d ", pos);
‎      break;
‎    }
‎  }
‎
‎  if (pos == -1)
‎    printf("Item Not found");
‎    
‎  return 0;
‎}

Linear Search Complexity

The linear search takes O(n) time to execute, where n is the number of elements in the array.