Table of Contents

URL: https://www.progressiverobot.com/linear-search-algorithm-c/

Linear Search is basically a sequential search algorithm.

In this algorithm, the key element is searched in the given input [array](/community/tutorials/arrays-in-c) in sequential order.

If the key element is found in the input array, it returns the element.

Linear Search Algorithm

linear search illustration for: Linear Search Algorithm

Linear_Search ( Array X, Value i)

  • Set j to 1
  • If j > n, jump to step 7
  • If X[j] == i, jump to step 6
  • Then, increment j by 1 i.e. j = j+1
  • Go back to step 2
  • Display the element i which is found at particular index i, then jump to step 8
  • Display element not found in the set of input elements.
  • Exit/End

Pseudo Code for Linear Search

				
					procedure LINEAR_SEARCH (array, key)

   for each item in the array
      if match element == key
         return element's index
      end if
   end for

end procedure

Implementation of Linear Search in C

  • Initially, we need to mention or accept the element to be searched from the user.
  • Then, we create a for loop and start searching for the element in a sequential fashion.
  • As soon as the compiler encounters a match i.e. array[element] == key value, return the element along with its position in the array.
  • If no values are found that match the input, it returns -1.
				
					#include <stdio.h> 

int LINEAR_SEARCH(int inp_arr[], int size, int val) 
{ 
	 
	for (int i = 0; i < size; i++) 
		if (inp_arr[i] == val) 
			return i; 
	return -1; 
} 


int main(void) 
{ 
	int arr[] = { 10, 20, 30, 40, 50, 100, 0 }; 
	int key = 100; 
	int size = 10; 
	int res = LINEAR_SEARCH(arr, size, key); 
	if (res == -1)
	printf("ELEMENT NOT FOUND!!");
    else
    printf("Item is present at index %d", res);
    
	return 0; 
}

Output:

				
					Item is present at index 5

Time Complexity of Linear Search

The best-case complexity is O(1) if the element is found in the first iteration of the loop.

The worst-case time complexity is O(n), if the search element is found at the end of the array, provided the size of the array is n.

—

Conclusion

Thus, in this article, we have understood and implemented Linear Search Algorithm.