Home About Contact Privacy Terms Disclaimer
TECHAntena
Last Updated On: June 19, 2016
Editor: Adeeb C

C++ program to search an element in an array using binary search

Category: C++,Programing
Tags

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.

  1.  [Initialize segment variables.]

Set BEG : = LB, END : = UB and MID = INT ((BEG + END)/2).

  1. Repeat Steps 3 and 4 while BEG<=END and DATA[MID]!=ITEM.

  2. 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