Linear Search is basically a **sequential search algorithm**.

In this algorithm, the key element is searched in the given input array in sequential order.

If the key element is found in the input array, it returns the element.

## Linear Search Algorithm

Linear_Search ( Array X, Value i)

**Set j to 1****If j > n, jump to step 7****If X[j] == i, jump to step 6****Then, increment j by 1 i.e. j = j+1****Go back to step 2****Display the element i which is found at particular index i, then jump to step 8****Display element not found in the set of input elements.****Exit/End**

## Pseudo Code for Linear Search

```
procedure LINEAR_SEARCH (array, key)
for each item in the array
if match element == key
return element's index
end if
end for
end procedure
```

## Implementation of Linear Search in C

- Initially, we need to mention or accept the element to be searched from the user.
- Then, we create a for loop and start searching for the element in a sequential fashion.
- As soon as the compiler encounters a match i.e. array[element] == key value, return the element along with its position in the array.
- If no values are found that match the input, it returns -1.

```
#include <stdio.h>
int LINEAR_SEARCH(int inp_arr[], int size, int val)
{
for (int i = 0; i < size; i++)
if (inp_arr[i] == val)
return i;
return -1;
}
int main(void)
{
int arr[] = { 10, 20, 30, 40, 50, 100, 0 };
int key = 100;
int size = 10;
int res = LINEAR_SEARCH(arr, size, key);
if (res == -1)
printf("ELEMENT NOT FOUND!!");
else
printf("Item is present at index %d", res);
return 0;
}
```

**Output:**

```
Item is present at index 5
```

**Time Complexity** of Linear Search

The best-case complexity is **O(1)** if the element is found in the first iteration of the loop.

The **worst-case time complexity is O(n)**, if the search element is found at the end of the array, provided the size of the array is n.

## Conclusion

Thus, in this article, we have understood and implemented Linear Search Algorithm.