Program for Linear Search in C++ and its Efficiency

Linear Search is the simplest search algorithm that can applied for a collection of data . Consider collection of data in the form of an array . To search an element or data from the Given list , Searching Algorithms play a major role . Linear Search refers to comparing the data sequentially with the other data in the list or array .

Also check : Program for Bubble sort in C++

Program for Linear Search in C++

#include<iostream>
using namespace std;
int main()
{
int arr[20];
int n;
int i;
while(1)
{
cout<<"\nEnter the number of elements in the array:";
cin>>n;
if(n>0&&(n<=20))
break;
else
cout<<"\n Array size exceeded Maximum 20 elements \n\n";
}
cout<<"\n#############################\n";
cout<<"Enter any elements\n";
cout<<"\n#############################\n";
for(i=0;i<n;i++)
{
cout<<"<"<<(i+1)<<">";
cin>>arr[i];
}
char ch;
int ctr;
do{
int data;
cout<<"\nEnter the element you want to search:";
cin>>data;
ctr=0;
for(i=0;i<n;i++)
{
ctr++;
if(arr[i]==data)
{
cout<<"\n"<<data<<" Found at position "<<i+1<<endl;
break;
}
}
if(i==n)
{
cout<<endl<<data<<"not found in the array\n";
cout<<"\n Number of comparisions:"<<ctr;
cout<<"\n\nContinue search (y/n):";
cin>>ch;
}
}while((ch=='y')||(ch=='Y'));
return 0;
}

Output of Linear search Program :

After compilation of the above code in Linux or latest compilers the output is as shown below .

Efficiency of Linear search :

When searching an element in an array , if the search element is found at the first position then only one comparision is required . The best case Timing complexity  for linear search is O(1) .

When the search element is at last position of the array or if it does not exit , you need to make n comparisons , where n is number of elements in the array . The worst case Timing complexity of linear search is O(n) .

FeedBack :

If I have missed anything please get it to me through comments . Also share your ideas and experience through comments .