loader image
Teachics

Linear Search

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.

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

linear search array to be searched
Array to be searched

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

working of linear search algorithm
Compare with each element

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

linear search algorithm element found in the array
Element found at i = 3

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.

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments