/* Program to implement binary Search algorithm*/
#include <iostream>
using namespace std;
int flag;
class Search
{
private:
int element[100],index,counter,start,last,mid;
public:
void getdata()
{
cout<<"\\nHOW MANY ELEMENTS DO YOU WANT TO ENTER : ";
cin>>counter;
cout<<"\\nENTER THE ELEMENTS OF THE ARRAY : ";
for (index=0;index<counter;index++)
{
cout<<"\\nENTER ELEMENT "<<index+1<<" : ";
cin>>element[index];
}
start=0;
last=counter-1;
}
void bubble() //function sorts the elements of array using bubble sort
{
int index = 0,index2 = 0,temp = 0;
for(index = 0; index < counter-1; index++)
{
for(index2 = 0; index2 < counter-1; index2++)
{
if(element[index2] > element[index2+1])
{
temp = element[index2];
element[index2] = element[index2+1];
element[index2+1] = temp;
}
}
}
}
void binarySearch(int num) //function searches the element using binary search
{
int low = start, high = last, position = 0, mid = 0;
bool found = false;
// loop till high is greater than low or till the element is not found
while (low <= high && found == false) {
// calculate the mid value
mid = (low + high) / 2;
// compare the mid value with the element
// if equal then print the position and return
if (element[mid] == num) {
position = mid;
found = true;
break;
}
// else if the middle value if greater than the element
// then element lies on the left side of the mid so decrease high value
else if (element[mid] > num) {
high = mid - 1;
}
// else if the middle value if less than the element
// then element lies on the right side of the mid so increase low value
else if (element[mid] < num) {
low = mid + 1;
}
}
// display this if element not found
if (found == false) {
cout<<"Element not Found in the Array";
return;
}
cout<<"Element found at position "<<mid + 1;
return;
}
};
int main()
{
Search s1;
int cont=0,element=0;
s1.getdata();
s1.bubble();
cout<<"\\nTHE ELEMENTS OF THE ARRAY HAVE BEEN SORTED ";
do
{
cout<<"\\nENTER THE ELEMENT TO BE SEARCHED : ";
cin>>element;
flag=0;
s1.binarySearch(element);
cout<<"\\nDO YOU WANT TO CHECK AGAIN (1/0):";
cin>>cont;
}while(cont==1);
return 0;
}
/******************************OUTPUT**********************************
HOW MANY ELEMENTS DO YOU WANT TO ENTER : 10
ENTER THE ELEMENTS OF THE ARRAY :
ENTER ELEMENT 1 : 45
ENTER ELEMENT 2 : 95
ENTER ELEMENT 3 : 75
ENTER ELEMENT 4 : 15
ENTER ELEMENT 5 : 35
ENTER ELEMENT 6 : 62
ENTER ELEMENT 7 : 2
ENTER ELEMENT 8 : 98
ENTER ELEMENT 9 : 48
ENTER ELEMENT 10 : 12
THE ELEMENTS OF THE ARRAY HAVE BEEN SORTED
ENTER THE ELEMENT TO BE SEARCHED : 12
THE ELEMENT 12 HAS BEEN FOUND ON 1 POSITION
DO YOU WANT TO CHECK AGAIN (1/0):1
ENTER THE ELEMENT TO BE SEARCHED : 100
THE ELEMENT 100 WAS NOT FOUND
DO YOU WANT TO CHECK AGAIN (1/0):1
ENTER THE ELEMENT TO BE SEARCHED : 1
THE ELEMENT 1 WAS NOT FOUND
DO YOU WANT TO CHECK AGAIN (1/0):1
ENTER THE ELEMENT TO BE SEARCHED : 48
THE ELEMENT 48 HAS BEEN FOUND ON 5 POSITION
DO YOU WANT TO CHECK AGAIN (1/0):0
Process returned 0 (0x0)
Press any key to continue.
*/