Code : (A1.cpp)
//============================================================================
// Name : A1.cpp
// Author : Nikita Kotak
// Version :
// Copyright : Your copyright notice
// Description : Binary Search in C++, Ansi-style
//============================================================================
#include <iostream>
#include <stdlib.h>
using namespace std;
class BinarySearch
{
public:
int binary_search(int *array, int upper,int lower, const int key);
void quick_sort(int *array,int lower,int upper);
int partition(int *array,int lower,int upper);
};
int BinarySearch:: binary_search(int *array, int upper,int lower, const int key)
{
upper = upper - 1;
int middle = (lower + upper) / 2; //divide and conquer strategy
while (lower <= upper)
{
if (array[middle] == key)
return middle;
else if (array[middle] > key)
upper = middle - 1; // change upper position
else
lower = middle + 1; // change lower position
middle = (lower + upper) / 2; //new middle element's position
binary_search(array, upper, lower, key);
}
return -1;
}
void BinarySearch::quick_sort(int *array,int lower,int upper)
{
int j;
if(lower<upper) //recursive quick sort for sorting elements for binary search
{
j=partition(array,lower,upper);
quick_sort(array,lower,j-1);
quick_sort(array,j+1,upper);
}
}
int BinarySearch::partition(int *array,int lower,int upper)
{
int pivot,i,j,temp;
pivot=array[lower];
i=lower;
j=upper+1;
do //partitioning function for quick_sort
{
do
i++;
while(array[i]<pivot&&i<=upper);
do
j--;
while(pivot<array[j]);
if(i<j)
{
temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}while(i<j);
array[lower]=array[j];
array[j]=pivot;
return(j);
}
int main()
{
BinarySearch obj;
cout << "\n\nBinary Search";
int length, key, choice = 1;
cout << "\n\nEnter the length of an array: ";
cin >> length;
int *array=new int[length];
cout << "\nEnter the elements: ";
for (int i = 0; i < length; i++)
cin >> array[i];
obj.quick_sort(array,0,length-1);
cout << "\nSorted array: [ ";
for (int i = 0; i < length; i++)
cout << array[i] << " ";
cout << "]";
while (choice != 0) {
cout << "\n\nEnter element to be searched: ";
cin >> key;
int result = obj.binary_search(array, length,0, key);
if (result != -1)
cout << "\n\n" << key << " found in the array at index " << result+1 << ".\n\n";
else
cout << "\n\n Element " << key << " not found in the given array.\n\n";
cout << "\n Do you want to continue(1/0)?";
cin >> choice;
}
return 0;
}
Output :
//============================================================================
// Name : A1.cpp
// Author : Nikita Kotak
// Version :
// Copyright : Your copyright notice
// Description : Binary Search in C++, Ansi-style
//============================================================================
#include <iostream>
#include <stdlib.h>
using namespace std;
class BinarySearch
{
public:
int binary_search(int *array, int upper,int lower, const int key);
void quick_sort(int *array,int lower,int upper);
int partition(int *array,int lower,int upper);
};
int BinarySearch:: binary_search(int *array, int upper,int lower, const int key)
{
upper = upper - 1;
int middle = (lower + upper) / 2; //divide and conquer strategy
while (lower <= upper)
{
if (array[middle] == key)
return middle;
else if (array[middle] > key)
upper = middle - 1; // change upper position
else
lower = middle + 1; // change lower position
middle = (lower + upper) / 2; //new middle element's position
binary_search(array, upper, lower, key);
}
return -1;
}
void BinarySearch::quick_sort(int *array,int lower,int upper)
{
int j;
if(lower<upper) //recursive quick sort for sorting elements for binary search
{
j=partition(array,lower,upper);
quick_sort(array,lower,j-1);
quick_sort(array,j+1,upper);
}
}
int BinarySearch::partition(int *array,int lower,int upper)
{
int pivot,i,j,temp;
pivot=array[lower];
i=lower;
j=upper+1;
do //partitioning function for quick_sort
{
do
i++;
while(array[i]<pivot&&i<=upper);
do
j--;
while(pivot<array[j]);
if(i<j)
{
temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}while(i<j);
array[lower]=array[j];
array[j]=pivot;
return(j);
}
int main()
{
BinarySearch obj;
cout << "\n\nBinary Search";
int length, key, choice = 1;
cout << "\n\nEnter the length of an array: ";
cin >> length;
int *array=new int[length];
cout << "\nEnter the elements: ";
for (int i = 0; i < length; i++)
cin >> array[i];
obj.quick_sort(array,0,length-1);
cout << "\nSorted array: [ ";
for (int i = 0; i < length; i++)
cout << array[i] << " ";
cout << "]";
while (choice != 0) {
cout << "\n\nEnter element to be searched: ";
cin >> key;
int result = obj.binary_search(array, length,0, key);
if (result != -1)
cout << "\n\n" << key << " found in the array at index " << result+1 << ".\n\n";
else
cout << "\n\n Element " << key << " not found in the given array.\n\n";
cout << "\n Do you want to continue(1/0)?";
cin >> choice;
}
return 0;
}
Output :
