C Program to search for an item using Linear Search

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:

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:

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:

Expected Output:

1st run:

2nd run:

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:

Leave a Comment

%d bloggers like this: