Design and Analysis of Algorithms

Go Back to List

Program to search the desired element from the list using Binary search.

 

#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int a[20],i,j,temp,n;
                                                                                //INPUT DATA
cout<<"\n Enter the size of the list ";
cin>>n;
cout<<"\nEnter the elements of the list ";
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=n;i++)
for(j=1;j<=n-1;j++)
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
int num;
cout<<"\nEnter the number to be searched ";
cin>>num;
int mid,beg=1,end=n,pos=0,flag='f';
while(beg<=end&&flag=='f')
{
mid=(beg+end)/2;
if(a[mid]==num)
{
pos=mid;
flag='t';
}
else
{
if(num>a[mid])
beg=mid+1;
else
end=mid-1;
}
}
if(flag=='t')
{
cout<<"\nThe number is present in the array ";
cout<<"\nThe position of no. is "<<pos;                              //SUCCESSFUL SEARCH
}
else
{
cout<<"\nThe number is not present in the list ";                 //UNSUCCESSFUL SEARCH
}
getch();
}

 

Output:

Enter the size of the list 5

Enter the elements of the list 1
2
3
4
5

Enter the number to be searched 5

The number is present in the array
The position of no. is 5

Analysis of Binary Search:

 Best Case: O(1)
 Average Case: O(log N)
 Worst Case: O(log N)
 Unsuccessful Search: O(log N)

Worst case
A worst input causes the algorithm to keep searching until low>high
We count number of comparisons of a list element with x per recursive call.
Assume 2k <= n < 2k+1 ; k = lg n

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.