In this article at OpenGenus, we have explained Linear search algorithm and implement a program on the same in C programming language.

Learn more:

• Try these questions if you think you know Linear Search
• Time & Space Complexity of Linear Search
• Master C Programming

Table of contents

• Problem statement
• How linear search works
• Time complexity
• Drawbacks of linear search
• Implementation of Linear Search in C
• Output
• Conclusion

Problem statement

In this article we will learn Linear search algorithm.

• Linear search algorithm is used to search an element in a given set of elements.
• It starts searching from one end of the array and goes on sequentially till it finds the element.

How Linear search works

Following is how linear search works:

• For example if the given array is {2,4,3,7,13,87,23,90,45,1}
• The element to find is 90.
• So according to linear search, searching will start from he zero position of the array.
• Then we check if the element at 0th index is equal to 90.
  {2,4,3,7,13,87,23,90,45,1}
  ..^
  It's not equal so we move to the next index.
• Again we check if the element at 1st index is equal to 90.
  {2,4,3,7,13,87,23,90,45,1}
  .....^
  It's not equal so we move to the 2nd index.
• Now is the element at 2nd position is equal to 90.
  {2,4,3,7,13,87,23,90,45,1}
  .........^
  It's not equal so we move to the 3rd index.
• Is the element at 3rd index is equal to 90.
  {2,4,3,7,13,87,23,90,45,1}
  ............^
  It's not equal so we move to the 4th index.
• Is the element at 4th index is equal to 90.
  {2,4,3,7,13,87,23,90,45,1}
  ................^
  It's not equal so we move to the 5th index.
• Is the element at 5th index is equal to 90.
  {2,4,3,7,13,87,23,90,45,1}
  .....................^
  It's not equal so we move to the 6th index.
• Is the element at 6th index is equal to 90.
  {2,4,3,7,13,87,23,90,45,1}
  ...........................^
  It's not equal so we move to the 7th index.
• Is the element at 7th index is equal to 90.
  {2,4,3,7,13,87,23,90,45,1}
  .................................^
  It's equal so we return the position 7.

Time complexity

• Best case time complexityof linear search is O(1) that is the element is present at 0th position of the array.
• Worst case time complexity of linear search is O(N), N being the number of elements in the array and the desired number is present at the last position.

Drawbacks of Linear search

• Since linear search is a sequential search algorithm and it's time complexity being O(N), makes it slow for large data/ large arrays.

Implementation of Linear Search in C

Following is the implemention of the code in C programming language:

// Part of iq.opengenus.org
#include <stdio.h>
 
int search(int arr[], int n, int x)
{
    int i;
    for(i=0;i<n;i++)
    {
        if (arr[i] == x)
            return i;
    }
    return -1;
}
int main(void)
{
    int arr[] = { 2,4,3,7,13,87,23,90,45,1};
    int x =90;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = search(arr,n, x);
    if(result == -1)
        printf("Element is not present in array");
    else
    printf("Element is present at index %d", result);
    return 0;
}

Output

Run the code as follows:

gcc code.c
./a.out

Following is the output of the program:

Element is present at index 7

Conclusion

• Linear search is one the most simple searching algorithms and can be used in both sorted and unsorted data.