**Linear Search** is the most basic searching algorithm. It is also know as **Sequential Search**.

## Linear Search Algorithm

Linear Search is a brute force algorithm. It sequentially checks each element of the array/list until a match is found or all the elements have been searched. Also, it doesn’t depend on the arrangement of elements in an array, unlike Binary Search which is applicable only if the array is sorted.

We traverse each element of the array using a loop and compare it with the search value.

### Steps

- Let
**N**be the length of array**arr**. - Let
**X**be the value we want to search in**arr**. - Initialize
**i = 0**. - Repeat the following steps while
**i < N**- If
**arr[i] is equal to X**then**X**is present in**arr**at index**i**.- Exit the program.

**i = i+1**.

- If
**X**is not present in**arr**.

### Pseudo Code

arr: Array to search n: Length of arr x: value to search FUNCTION LINEAR_SEARCH ( arr, n, x ) FOR i = 0 TO n-1 DO IF arr[i] == x THEN PRINT x is present in the array at Index i RETURN END IF END FOR PRINT x is not present in the array RETURN END FUNCTION

### Program

```
#include<stdio.h>
void linear_search(int arr[], int n, int x) {
int i;
for (i = 0; i < n; ++i) {
if (arr[i] == x) {
printf(" %d is present in the array at index %d\n", x, i);
return;
}
}
printf(" %d is not present in the array\n", x);
}
int main()
{
int x, n;
int arr[] = { 5,8,1,2,13,7,9,10,11,6 };
// length of array
n = sizeof(arr) / sizeof(int);
printf("\n\n Enter value you want to search: ");
scanf("%d", &x);
linear_search(arr, n, x);
}
```

**Output**

### Time Complexity of Linear Search

**Best Case**: O(1)

When the value we want to search is the first element of the array.

**Worst Case**: O(N)

When the value we want to search is not present in the array.

**Average Case:** O(N)

On average, we can assume that the data is present in the middle of the array. Therefore, the time complexity is O(N/2), but constants are ignored. Thus, the time complexity is O(N).

*Space Complexity of Linear Search is O(1).*

## Linear Search Using Recursion (Recursively)

Linear search algorithm can also be implemented using recursion. This method is not widely used. This is because the space complexity of recursive implementation is **O(N)** and it is comparatively more complex than iterative approach.

Each recursive call compares the **ith** element of the array with the search value. If the search value is found, we simply return **i**. If the search value is not found, we increment **i** and call the recursive function.

### Steps

- If
**i == N**Return**-1**. - If
**arr[i] == X**then- Return
**i**.

- Return
- Else
- Return
**linear_searchR(arr,N,i+1,X)**.

- Return

### Pseudo Code

arr: Array to search N: Length of arr X: value to search FUNCTION linear_searchR ( arr, N, i , X ) IF i == N THEN RETURN -1 ELSE IF arr[i] == X THEN RETURN i ELSE RETURN linear_searchR( arr, N, i+1, X) END IF END FUNCTION

### Program

```
#include<stdio.h>
int linear_searchR(int arr[], int n, int i, int x) {
// i==n implies we have checked all elements of the array
if (i == n) {
return -1;
}
else if (arr[i] == x) {
return x;
}
else {
return linear_searchR(arr, n, i + 1, x);
}
}
int main()
{
int x, n, idx;
int arr[] = { 5,8,1,2,13,7,9,10,11,6 };
// length of array
n = sizeof(arr) / sizeof(int);
printf("\n\n Enter value you want to search: ");
scanf("%d", &x);
idx = linear_searchR(arr, n, 0, x);
if (idx == -1) {
printf(" %d is not found in the array \n", x);
}
else {
printf(" %d is present in the array at index %d \n", x, idx);
}
}
```

**Output**

*The time complexity of recursive implementation is same as iterative (loop) implementation.*

## Advantages of Linear Search

- It doesn’t depend upon the arrangement of elements in the array.
- It works efficiently if the number of insertion operations is very large compared to search operations. Insertion in an unsorted array takes O(1) comparisons whereas insertion in the sorted array takes O(N) comparisons. If the number of insert/update operations is very large, binary search becomes very inefficient.
- It can search for data in a linked list whereas binary search only applies to arrays.

## Disadvantages of Linear Search

- If the number of search queries is very large in comparison to insert/update then the program becomes very inefficient.