×

Search anything:

# Linear Search explained simply [+ code in C]

#### Algorithms Search Algorithms

Get this book -> Problems on Array: For Interviews and Competitive Programming

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

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

# Problem statement

• 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.