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.

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 complexity**of 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.