What is Linear Search in C?

Introduction to Linear search in C

In data structures, searching is the technique of finding elements from the given data sets. There are many algorithms present to do so and Linear search is one of them.

If we compare each element in the array to search an element then it is considered as a sequential search. But if we are comparing only a few elements and skipping some of them then it is considered as an interval searching

And Linear search is the sequential search algorithm as it sequentially searches for the key element against all the elements one by one until the element is found or the list has been traversed completely. It is the least complex algorithm present for searching.

As a result of the search, it returns the location where the key is found, else it returns null.

Approach For Linear search in C

Linear search in C can be implemented using an iterative method or the recursive method.

Below, A is a unique set of elements of size 10. If there are multiple copies of an element it may return only the location of one and may not be able to reach another copy of it.

We can also perform a linear search on a list that has repeated elements but it is considered best practice to choose a unique set of elements.

Here, Key=7, The Key is referred to the element we’re searching for.

Simple Approach to do a linear search in C

• Start from the 0th index of the list and compare the key element with each element one by one present in the list.
• If the key matches with an element, return the index of the element.
• If the key doesn’t match with any of the elements, return -1 or NULL.

Linear search in C programme (Iterative method)

#include<stdio.h>
void main ()  
{  
    int a[10] = {10,32, 40, 15, 2, 9, 18, 13, 60, 9};
    int key, i,flag;  
    printf("Enter key\n");  
    scanf("%d",&key);  
     for (i = 0; i< 10; i++)  
     {  
          if(a[i] == key) 
          {  
              flag = i+1;  
              break;  
           }   
           else   
           flag = 0;  
     }    
     if(flag != 0) 
     {  
          printf("Element found at index %d \n",flag);  
    }  
   else 
    {  
         printf("Element not found\n"); 
    }  
}   

Example Input : key = 2; Output : Element found at index 4

Recursive Approach

A Linear search programme can also be implemented through recursion in C.

• In this C Programme, a recursive function called LinearSearch() is created, which takes in 4 parameters and returns the location of an element that is searched by the user.
• If the element is found at the first index, we return the index.
• Else if it is not then the size of the array is decreased by 1, the first element of the array is eliminated, which means when the LinearSearch() is called the second time the size of the array will be (n-1). This process is repeated until the element is found.

#include<stdio.h>
 /* Recursive function */
int LinearSearch(int A[], int l, int r, int key)
{
     if (r < l)
        return -1;
     if (A[l] == x)
        return l;
     if (A[r] == x)
        return r;
     return LinearSearch(A, l+1, r-1,key);
}
 
int main()
{
    int A[] = {21, 4, 84, 9, 10},
    int  i;
    int n = sizeof(A)/sizeof(A[0]);
    int key = 3;
    int location = LinearSearch(A, 0, n-1, key);
    if (location != -1)
       printf("Element %d is present at index %d",key, location);
    else
        printf("Element %d is not present",key);
    return 0;
}

Output: 
Element 3 is present at index 4

Note: The Iterative approach for implementing linear search in C  is faster. Also, the recursive programme takes more space in the memory.

Time complexity of Linear Search in C

• For both cases, In the worst case, a linear search algorithm takes O(n) operations.
• In the best case, a linear search algorithm takes O(1) operations.

Linear search optimisation In C

It is observed that when you are searching for any key then there is a possibility that you search for the same element again.

There are two methods to improve linear search in C. 

1. Transposition

If we are searching for an element suppose five then what we want as it should be searched faster the next time.

One thing you could do is you can swap the location of 5 with the previous element. So it will reduce by one step a second time. Every time whenever you are searching for the same element, it will be coming closer. This method is called transposition.

Pseudo Code:

for(i=0;i<length;i++)
{
if(key == A[i]){
swap(A[i],A[i-1]
   return i;
}
}

2. Move to the front head

This method is called the move to the front or move to head as the key after getting found is swapped with the value present at the starting index. The next time when we search for the element it is found just in constant time.

Pseudo Code:

for(i=0;i<length;i++){
if(key == A[i]){
swap(A[i],A[i-1]
   return i;
}
}

Note: These methods do not improvise the linear search performance for every possible case.

Advantages of Linear Search in C

• Performs fast searching for list smaller in size
• The list on which linear search is applied need not be sorted.
• The addition or deletion of elements does not affect linear search as the list need not be sorted.

Frequently Asked Questions

Key Takeaways

As Linear search is the simplest searching algorithm and can be performed using functions and loops in C, it is rarely used practically because it is only useful in situations where the list is small in size.

Commonly asked interview questions are what is linear search, how it is implemented, optimization, etc. Preparing for an interview?

Check out our awesome course –Interview preparation guide

To know more about searching, you can choose our course. Free trial available!

By Aakriti Jain