C++ program to search an element in an array using binary search
Aim:
To write a program to search an element in an array using binary search.
Algorithm:
BINARY(DATA, LB, UB, ITEM, LOC)
Here DATA is a sorted array with lower bound LB and upper bound UB, and ITEM is a given item o information. The variables BEG, END and MID denote, respectively, the beginning, end and middle locations of a segment of elements of DATA. This algorithm finds the location LOC of ITEM in DATA or sets LOC=NULL.
- [Initialize segment variables.]
Set BEG : = LB, END : = UB and MID = INT ((BEG + END)/2).
- Repeat Steps 3 and 4 while BEG<=END and DATA[MID]!=ITEM.
-
If ITEM<DATA[MID, then:
Set END : = MID – 1.
Else:
Set BEG : = MID+1.
[End of if structure]
4. Set MID : = INT((BEG + END )/2)
[END of Step 2 loop.]
5. If DATA[MID] = ITEM, then:
Set LOC : = MID
Else:
Set LOC : = NULL.
[End of If structue.]
6. Exit.
Program code:
#include<iostream.h>
#include<conio.h>
class binary
{
int b,e,m,a[20],n,s,k,j,i,t;
public:
void read()
{
cout<<"Enter the number of elements : ";
cin>>n:
cout<<"\nEnter the elements : ";
for(i=1;i<=n;i++)
{
cin>>a[i];
}
cout<<"Sorted array is \n";
for(k=1;k<=n;k++)
{
for(j=1;j<=n;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
}
void display()
{
for(i=0;i<=n;i++)
cout<<a[i]<<"\t";
}
void search()
{
cout<<"\nEnter the element to search : ";
cin>>s;
b=1;
e=n;
m=((b+e)/2);
while((b<=e)&&(a[m]!=s))
{
if(s<a[m])
{
e=m-1;
}
else
{
b=m+1;
}
m=((b+e)/2);
}
if(a[m]==s)
{
cout<<s<<"found in"<<"position"<<m;
}
else
{
cout<<"Element not founded : ";
}
}
};
void main()
{
clrscr();
binary b;
b.read();
b.display();
b.search();
getch();
}
Output:
Enter the number of elements : 4
Enter the elements : 1 2 3 4
Enter the number to search : 3
Eleent found at position 3
