Design and Analysis of Algorithms
| Program to search the desired element from the list using linear search. |
#include<iostream.h>
#include<conio.h>
void main()
{
int c,i,n,b,s[10],sl;
clrscr();
//INPUT DATA
cout<<"\n Enter the no. of elements: ";
cin>>n;
cout<<"\n Enter the no.s : ";
for(i=1;i<=n;i++)
{
cout<<"num ["<<i<< "]=";
cin>>s[i];
}
cout<<"Enter the no. you want to search: ";
cin>>sl;
i=1;
//INITIALIZE COUNTER
while(i<=n)
// SEARCH FOR ITEM
{
b=s[i]-sl;
if(b==0)
{
c=i;
break;
}
else
{
c=0;
}
i++;
}
if(c==0)
//SEARCH SUCCESSFUL OR NOT
{
cout<<"\n search unsuccessful";
}
else
{
cout<<"\n search successful and the location is: "<<c;
}
getch();
}
| Output: |
Enter the no. of elements: 4
Enter the no.s : num [1]=23
num [2]=45
num [3]=1
num [4]=67
Enter the no. you want to search: 1
search successful and the location is: 3
| Analysis of Linear Search: |
The complexity of the above program is measured by the number of
comparisons f(n) required to find ‘s1’ in ‘s’ where ‘s’ contains
n items.
Worst case occurs when one has to search through entire array
‘s’ i.e. item does not appear in ‘s’. Thus algorithm requires:
f(n) = n+1 comparisons
Average case running time is measured using probabilistic notion
of expectation and is found to be
f(n) = (n+1)/2
Thus the average number of comparisons required to find the
location of ‘s1’ is approximately equal to the half number of
elements in the array.
If any of you want to submit your programs and
contribute to site please mail us at:
citysuvidha@gmail.com
Click here to have a look at List of programs
You can download all the programs in a zip file also. For this you have to do one thing. Just register at the citysuvidha forum and start any thread of any topic. Once you start the thread and put your request, admin will automatically send you the desired zip file.