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.