×

Search anything:

Linear Search explained simply [+ code in C]

Binary Tree book by OpenGenus

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

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

Learn more:

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.
Linear Search explained simply [+ code in C]
Share this