Please write a C++ program that performs the binary search algorithm. Binary sea
ID: 644415 • Letter: P
Question
Please write a C++ program that performs the binary search algorithm. Binary search algorithm finds the position of target value (search key) within a sorted array. For the purpose of simplicity, we assume that the array has been sorted in an ASCENDING order. The concept of binary search is to split the sorted array in half and then, rule out the half of data at each step or iteration. In each step, the search algorithm compares the search key against the key value in the middle of array. If the search key matches the key value in the middle of array, then the index of middle element is returned. If the search key is less than the key value in the middle of array, then the search algorithm repeats its actions on the left half of array (left sub-array). Otherwise, the search algorithm repeats its action on the right half of array (right sub-array).
Before implementation, it is recommended to perform hands-on simulation in the following scenarios to better comprehend the binary search algorithm. Assume we have an array of 9 integers in an ascending order: 2, 4, 6, 8, 10, 12, 14, 16, 18. Please perform the binary search algorithm on the following key values: 10, 4, 18, 0 and 100.
Here is a possible scenario. When the program starts, it asks the user how many numbers should be read from the input file. In this homework assignment, the text file,
Explanation / Answer
Program code:
// BinarySearchAlgorithm.cpp : Defines the entry point for the console application.
//header files
#include "stdafx.h"
#include <iostream>
using namespace std;
//function prototypes
int* initializeArray(int nRead);
int* sort(int *A, int size);
int binarySearch(int *A, int value, int start, int end);
//main function definition
int main()
{
//declare the required variables
int size,size1, size2;
int value;
int x,y;
//prompt the user to enter the size of the array
cout<<"Enter the size of the array: ";
cin>>size;
//create a pointer array
int* A=NULL;
A=new int[size];
A=initializeArray(size);
A=sort(A,size);
for(int i=0;i<size;i++)
cout<<A[i]<<" ";
cout<<endl;
//prompt the user to enter the value to search
cout<<"Enter the value to search: ";
cin>>value;
//assign the values of size1 and size2 by dividing the size of the
//Actual array
size1=size/2;
//call the binarySearch function by passing the values
x=binarySearch(A, value, 0, size1);
y=binarySearch(A, value, size1, size);
//depending on the values of x and y print the message to the user
if (x<0 && y<0)
cout<<"Sorry! The value is not found.";
else if (x>-1)
cout<<"The value is found at "<<(x+1);
else if( y > -1 )
cout<<"The value is found at "<<(y+1);
cout<<endl;
system("pause");
return 0;
}
int* initializeArray(int nRead)
{
int *arr=new int[nRead];
//prompt the user to enter the elements to store in an array
cout<<"Enter the array values: ";
for(int i=0;i<nRead;i++)
cin>>arr[i];
return arr;
}
//sort fucntion
int* sort(int *A, int size)
{
int i, j;
int temp=0;
for(i=0;i<size;i++)
{
for(j=0;j<size-1;j++)
{
if(A[j]>A[j+1])
{
temp=A[j];
A[j]=A[j+1];
A[j+1]=temp;
}
}
}
return A;
}
//binarySearch function
int binarySearch (int *arr, int value, int left, int right)
{
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if( arr[mid] == value )
{
return mid;
}
else if (arr[mid] > value)
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return -1;
}
Sample output:
Enter the size of the array: 10
Enter the array values: 2
4
6
8
10
12
16
18
20
14
2 4 6 8 10 12 14 16 18 20
Enter the value to search: 10
The value is found at 5
Press any key to continue . . .
Enter the size of the array: 10
Enter the array values: 2
4
6
8
10
12
14
16
18
20
2 4 6 8 10 12 14 16 18 20
Enter the value to search: 100
Sorry! The value is not found.
Press any key to continue . . .
Note:
This file will generate the 1000 numbers (programmer choice whether to create random or continuous (code is kept in comments)). Initializes the array by reading the data from the file depending on the size passed and prompts the user to enter the search element and prints the position of the element if found else prints an error message
// BinarySearchAlgorithm.cpp : Defines the entry point for the console application.
//header files
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <time.h>
using namespace std;
//function prototypes
int* initializeArray(int nRead);
int* sort(int *A, int size);
int binarySearch(int *A, int value, int start, int end);
//main function definition
int main()
{
//declare the required variables
int size,size1, size2;
int value;
int x,y;
srand(time(NULL));
//create a file that contains the 1000 numbers randomly
//generated
ofstream fileout("number_list.txt");
for(int i=0;i<1000;i++)
{
fileout<<i+1;
//if required to generate random numbers
//fileout<<rand()%1000
fileout<<endl;
}
fileout.close();
//prompt the user to enter the size of the array
cout<<"Enter the size of the array: ";
cin>>size;
//create a pointer array
int* A=NULL;
A=new int[size];
A=initializeArray(size);
//call the sort method so that if the file contains the random numbers then
//this method will be userful
A=sort(A,size);
for(int i=0;i<size;i++)
cout<<A[i]<<" ";
cout<<endl;
//prompt the user to enter the value to search
cout<<"Enter the value to search: ";
cin>>value;
//assign the values of size1 and size2 by dividing the size of the
//Actual array
size1=size/2;
//call the binarySearch function by passing the values
x=binarySearch(A, value, 0, size1);
y=binarySearch(A, value, size1, size);
//depending on the values of x and y print the message to the user
if (x<0 && y<0)
cout<<"Sorry! The value is not found.";
else if (x>-1)
cout<<"The value is found at "<<(x+1);
else if( y > -1 )
cout<<"The value is found at "<<(y+1);
cout<<endl;
system("pause");
return 0;
}
//initialize the Array by passing the size of the array
//this method reads the data from the file depending on the size passed
int* initializeArray(int nRead)
{
char filename[50];
int i=0;
int *arr=new int[nRead];
cout<<"Enter the file name: ";
cin>>filename;
fstream myfile(filename);
if(myfile)
{
while(!myfile.eof())
{
if(i>nRead)
{
break;
}
myfile>>arr[i];
i++;
}
}
else
{
cout<<"Sorry! Unable to open the file."<<endl;
}
myfile.close();
return arr;
}
//sort fucntion
int* sort(int *A, int size)
{
int i, j;
int temp=0;
for(i=0;i<size;i++)
{
for(j=0;j<size-1;j++)
{
if(A[j]>A[j+1])
{
temp=A[j];
A[j]=A[j+1];
A[j+1]=temp;
}
}
}
return A;
}
//binarySearch function
int binarySearch (int *arr, int value, int left, int right)
{
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if( arr[mid] == value )
{
return mid;
}
else if (arr[mid] > value)
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return -1;
}
Sample input text file: number_list.txt
1
2
3
4
5
6
7
8
9
10
11
.
.
.
999
1000
Sample output:
Enter the size of the array: 20
Enter the file name: number_list.txt
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Enter the value to search: 8
The value is found at 8
Press any key to continue . . .