Linear Search - Algorithm and Program in C, C++, Python

In this post, we will see about Linear Search, its basic Algorithm, and implementing Linear Search using various programming languages like C, C++, Java, and Python.

INTRODUCTION

Linear Search is the simplest and least efficient method of searching elements from an array. This technique is often used when elements are stored without any consideration given to the order.

In Linear Search, we start searching from the first element of the array and compare each and every element till we found our desired element.

A real-life example of linear search is the collection of photographs from which you want to search for a particular photograph. You will start searching from the first photograph until you find the desired one or search till the last photograph. In this case, the strategy you are following to search for the desired photograph is sequential. When you are looking for the picture you were comparing each and every picture of the collection with that photograph in your mind. 

HOW LINEAR SEARCH WORKS?

In order to understand linear search, let us consider the above example in which we have 10 elements as shown. Suppose here we have to search for an element 33 in the array. 

To search for element 33 we will compare it with every element present in the array from the beginning and until we did not found our desired element we will continue our searching/comparing and here 33 elements exist in the array such that we found it at 7th position. 

LINEAR SEARCH ALGORITHM

LSEARCH(A, N, ITEM)

Given One dimensional Array 'A' with 'N' elements and ITEM to be searched. This algorithm finds and return the location LOC of ITEM in the array A or set LOC = -1 if the search is unsuccessful. Here LOC is the local variable.

  1. LOC = -1 [ Intialize Location Counter ]

  2. I = 1 [ Initialize Counter ]

  3. [ Search for ITEM ]

      Repeat while I <= N and A[ I ] != ITEM 

              I = I + 1

      [ End of loop ]

  4. If A[ I ] = ITEM then [ Successful ]

              LOC = I

      [ End of If Structure ]

  5. Return LOC

1. LOC = -1 [ Intialize Location Counter ] 2. I = 1 [ Initialize Counter ] 3. [ Search for ITEM ] Repeat while I <= N and A[ I ] != ITEM I = I + 1 [ End of loop ] 4. If A[ I ] = ITEM then [ Successful ] LOC = I [ End of If Structure ] 5. Return LOC

PROGRAM :

#----Linear Search----
array=[]
def linearSearch(n,item):
    # Going through array sequencially
    for i in range(0,n):
        if (array[i] == item):
            return i
    return -1

def takeinput(n):
print("\nEnter "+str(n)+" Elements of Array :")
for i in range(n):
data = int(input())
array.append(data)

#----main----
n = int(input("Enter Number of Element : "))
takeinput(n)
item = int(input("\n\nEnter Element to Search : "))
result = linearSearch(n,item)
if(result == -1):
    print("\n\tElement not found")
else:
    print("\nElement Found at Position : ",result+1)

#----Linear Search---- array=[] def linearSearch(n,item): # Going through array sequencially for i in range(0,n): if (array[i] == item): return i return -1 def takeinput(n): print("\nEnter "+str(n)+" Elements of Array :") for i in range(n): data = int(input()) array.append(data) #----main---- n = int(input("Enter Number of Element : ")) takeinput(n) item = int(input("\n\nEnter Element to Search : ")) result = linearSearch(n,item) if(result == -1): print("\n\tElement not found") else: print("\nElement Found at Position : ",result+1)

#include<iostream>
using namespace std;
int linearsearch(int a[],int n,int item)
{
int loc = -1;
for(int i=0;i<n;i++)
{
if(a[i]==item)
{
loc = i;
}
}
return loc;
}
int main()
{
int n;
cout<<"Enter Number of Element : ";
cin>>n;
int a[n],result,item;
cout<<"\nEnter "<<n<<" Elements of Array :"<<endl;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cout<<"\n\nEnter Element to Search : ";
cin>>item;
result=linearsearch(a,n,item);
if(result==-1)
{
cout<<"\n\tElement not found";
}
else
{
cout<<"\nElement Found at Position : "<<result+1;
}
return 0;
}

#include<iostream>using namespace std; int linearsearch(int a[],int n,int item) { int loc = -1; for(int i=0;i<n;i++) { if(a[i]==item) { loc = i; } } return loc; } int main() { int n; cout<<"Enter Number of Element : "; cin>>n; int a[n],result,item; cout<<"\nEnter "<<n<<" Elements of Array :"<<endl; for(int i=0;i<n;i++) { cin>>a[i]; } cout<<"\n\nEnter Element to Search : "; cin>>item; result=linearsearch(a,n,item); if(result==-1) { cout<<"\n\tElement not found"; } else { cout<<"\nElement Found at Position : "<<result+1; } return 0; }

#include<stdio.h>
int linearsearch(int a[],int n,int item)
{
int loc = -1;
for(int i=0;i<n;i++)
{
if(a[i]==item)
{
loc = i;
}
}
return loc;
}
int main()
{
int n;
printf("Enter Number of Element : ");
scanf("%d",&n);
int a[n],result,item;
printf("\nEnter %d Elements of Array :\n",n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("\n\nEnter Element to Search : ");
scanf("%d",&item);
result=linearsearch(a,n,item);
if(result==-1)
{
printf("\n\tElement not found");
}
else
{
printf("\nElement Found at Position : %d",result+1);
}
return 0;
}

#include<stdio.h>int linearsearch(int a[],int n,int item) { int loc = -1; for(int i=0;i<n;i++) { if(a[i]==item) { loc = i; } } return loc; } int main() { int n; printf("Enter Number of Element : "); scanf("%d",&n); int a[n],result,item; printf("\nEnter %d Elements of Array :\n",n); for(int i=0;i<n;i++) { scanf("%d",&a[i]); } printf("\n\nEnter Element to Search : "); scanf("%d",&item); result=linearsearch(a,n,item); if(result==-1) { printf("\n\tElement not found"); } else { printf("\nElement Found at Position : %d",result+1); } return 0; }

OUTPUT : 

COMPLEXITY :

In order to determine the complexity of the linear search algorithm, we must know the number of comparisons made between ITEM and A[I].  Therefore the Best Case occurs only when the element we are searching for is present at index 1 and in this scenario, Big-O will be expressed as O(1). 

The Wors Case when ITEM we are searching for is either at the last location of the array or it is not present in array A. So in this scenario, we need, n comparisons, and complexity in the Worst Case can be expressed as O(n).