## Linear Search

In linear search, we start searching for the target item at the beginning of the array. If the target is equal to the element at index 0, then we have found the target. Otherwise, we keep searching for the target one by one in the array until a match is found. The linear search also sometimes known as Sequential search.

We commonly use Linear search when the elements of an array are not sorted.

Let’s take an example:

Suppose, we have an array `arr`

declared and initialized as:

1 |
int arr[] = {100, 50, 99, 44, 12}; |

The following are the steps to search for value `44`

inside the array.

Step 1: Search for `44`

at index `0`

. Since, `44 != arr[0]`

, we move on to the next index.

Step 2: Search for `44`

at index `1`

. Since, `44 != arr[1]`

, we move on to the next index.

Step 3: Search for `44`

at index `2`

. Since, `44 != arr[2]`

, we move on to the next index.

Step 4: Search for `44`

at index `4`

. Since, `44 == arr[2]`

, we have found the target. At this point, we don’t need to move on to the next index. So, our search ends here.

## Time Complexity

Let’s now examine the efficiency of Linear search in term of Big O Notation.

In a worst-case scenario, if there are 100 elements in the array then the linear search will take 100 steps. Similarly, if there are 10 million elements in the array, then the linear search will take 10 million steps.

**Note**: By worst-case scenario, we mean that the target is found at the end of the array.

In general, we can say that in the worst-case scenario the linear search will take as many steps as there are elements in the array. Hence, If there are `N`

elements in the array, then the linear search would take `N`

steps.

The above statement can be expressed in terms of Big-O notation as follows:

1 |
O(N) |

This is read as big O of n.

Keep in mind that in plain English, `O(N)`

simply means for `N`

number of elements, an algorithm would take N number of steps.

## Linear Search C Program

The following is a C program to search for the target using Linear search algorithm:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
/*************************************************** * Program to search for an item using Linear Search ****************************************************/ #include<stdio.h> // include stdio.h #define SIZE 10 int main() { int arr[SIZE] = {100, 91, 22, 52, 71, 9, 11, 24, 2, 80}, is_found = 0; int target; // number to be searched printf("Enter element to search: "); scanf("%d", &target); // search for the target sequentially for(int i = 0; i < SIZE; i++) { if(target == arr[i]) { // if target is found stop the search and break out is_found = 1; break; } } if(is_found) { printf("Item %d found.", target); } else { printf("Item %d not found.", target); } // signal to operating system everything works fine return 0; } |

**Expected Output:**

1st run:

1 2 |
Enter element to search: 80 Item 80 found. |

2nd run:

1 2 |
Enter element to search: 200 Item 200 not found. |

## How it works

In line 13, we ask the user to input a number to be searched.

The `scanf()`

function in line 14 reads the input from the keyboard and stores it in the variable named `target`

.

In lines 17-25, we use a for loop to iterate over the elements in the array. If the target is equal to the current element in the array, we set `is_found`

to `1`

and break out of the for loop using the `break`

statement. Otherwise, we keep looking for the target until we have reached the end of the array.

The if-else statement in lines 27-34 checks the value of `is_found`

variable to determine whether we have found the target or not and displays the appropriate message.

**Recommended Reading:**