OverIQ.com

  1. Home
  2. C Programming Examples
  3. C Program to search for an item using Linear Search

C Program to search for an item using Linear Search

Last updated on September 23, 2020

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:

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

The following are the steps to search for value 44 inside the array.

  1. Search for 44 at index 0. Since, 44 != arr[0], we move on to the next index.
  2. Search for 44 at index 1. Since, 44 != arr[1], we move on to the next index.
  3. Search for 44 at index 2. Since, 44 != arr[2], we move on to the next index.
  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:

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;
}

Try it now

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:

C Programming Examples

Recent Posts