In this section of the tutorial, we will discuss the Linear Search in Data Structure. It is also known as Sequential Search. The Linear Search is used to locate an item in an array or list. In this tutorial, we will understand the concept used in Linear Search to find an item in a list, the algorithm of Linear Search and also we will implement the Linear Search in code using C and C++ to perform operations.

Now, let’s move further to the introduction of Linear Search.

What is Linear Search in Data Structure?

Linear Search is the most basic type of searching technique used in Data Structure whenever the list is not in an ordered form. The scope of Linear Search is limited to small lists or lists that are left unsearched in a Data Structure.

Successful Linear Search

Unsuccessful Linear Search

The above illustrated diagrams show two unordered lists where Linear Search is implemented. In the first diagram, the Linear Search was successful and in the second diagram, the Linear Search was unsuccessful.

Further, we will learn about the concept used in Linear Search in searching for a target.

Concept used in Linear Search

The concept used in using the Linear Search in searching for the target is pretty straightforward as it is simple and requires a minimal amount of code and logic to implement. It starts searching from the beginning of the list and termites when the target is found, otherwise keeps searching the next items in the list until the end is reached. A simple breakdown of the concept used in Linear Search is defined below.

• The algorithm starts with searching the target at the beginning of the list.
• The searching continues moving forward into the list until the target is found.
• The searching end either when the target is found or it is not present in the list.

There are two main possibilities deduced out of this concept:

• Either finding the target in the list.
• Or continue searching and reaching the end of the list.

Algorithm of Linear Search

Now, we will prepare an algorithm based on the above given concept of the Linear Search before we finally write the code for implementation.

The algorithm of the Linear Search is quite simple to write. Below are the convention of writing the algorithm of Linear Search.

• For the Linear Search algorithm, we need four parameters to find if the data is present in the list or not and if it is present, then at what location it is present.
• First, the list we have to search for.
• Second, an index to the last element of the list or the size of the list may be passed.
• Third, the target, if it is found.
• Fourth, the address where the target’s index location can be stored.

The algorithm of Linear Search is as follows:

Algorithm LinearSearch (list, last, target, addrs)
1 set key to 0
2 loop (key < last AND target not equal list[key])
1 increment key
3 end loop
4 set addrs to key
5 if (target equal list[key])
1 set found to true
6 else
1 set found to false
7 end if
8 return found
end LinearSearch

• Here, list is the list we are searching in.
• last is the index to the last element.
• target is the target we are searching in the list.
• addrs is the address where the target’s index value is stored.
• key is the variable that checks whether the target matches with the list item.

Working of Linear Search Algorithm

The working of the algorithm of Linear Search given above is as follows:

• The list we are working on must contain at least one element in it.
• last is index to the last element in the list.
• target holds the data value to be searched and located in the list.
• addrs is the address of index in calling algorithm.
• If the target is found, index location is stored in addrs and found is set to true.
• If the target is not found, last is stored in addrs and found is set to false.
• Now, return found true or false.

Time and Space Complexity of Algorithm

Linear Search Implementation

Now that we understand the concept of Linear Search and also we have written the algorithm of Linear Search, now we can implement Linear Search in a programming language to perform the operation. Here, we will implement Linear Search in C and C++.

Implementation in C

Code:

#include<stdio.h>
int main()
{
    int arr[8]={10,12,14,16,2,4,8,6};
    int a,x=0,i;
    printf("Enter a value to search in the array: ");
    scanf("%d",&a);

    for(i=0;i<=8;i++)
    {
        if(a==arr[i])
        {
            x=1;
            break;
        }
        else
        {
           x=0;
        }
    }
    if(x==1)
    printf("Data found at location arr[%d]\n",i);
    else
    printf("Data not found at any location\n"); 
    return 0;
}

Output:

Enter a value to search in the array: 8
Data found at location arr[6]

Implementation in C++

Code:

#include<iostream>
using namespace std;
int main()
{
    int arr[]={14,16,23,25,32,2,4,8,6,10,12};
    int a,x=0,i;
    cout<<"Enter a value to search in the array: ";
    cin>>a;
    int n=sizeof(arr)/sizeof(arr[0]);
    for(i=0;i<n;i++)
    {
        if(a==arr[i])
        {
            x=1;
            break;
        }
        else
        {
           x=0;
        }
    }
    if(x==1)
    cout<<"Data found at location arr["<<i<<"]\n";
    else
    cout<<"Data not found at any location\n"; 
    return 0;
}

Output:

Enter a value to search in the array: 2
Data found at location arr[5]

In the next section of the tutorial, we will discuss the Binary Search in Data Structure which is used to locate an item in an ordered collection of data items or array.