My job is to: Modify the binarySearch(…) function so that it will print out the
ID: 3710357 • Letter: M
Question
My job is to: Modify the binarySearch(…) function so that it will print out the number of comparisons used in the binarySearch(…) function. The output should say “**** 5 Comparisons from BinarySeach ****”, where 5 is the actual number of comparisons.
//CreateList.cpp
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ofstream outData;
outData.open("PrizeList.txt");
for (int count = 0; count < 20; count++)
outData << rand()%500 + 1 << endl;
return 0;
}
//Prize.cpp
/* The program Prize.cpp simulates a radio station that
asks the caller to guess a number. The number is
compared against a list of 20 numbers between 1
and 500 inclusive. The contest is held until a number
has been matched or a value of -1 is entered.
A message is displayed containing the winning number,
the location in the list of numbers, the number of
calls made, and the amount of the prize. */
/* An input file PrizeList.txt is used to enter the data. */
/* A message is displayed containing the winning number,
the location in the list of numbers, the number of
calls made, and the amount of the prize. */
//header files
/* use the correct preprocessor directives for
input/output and file stream */
#include <iostream>
#include <fstream>
using namespace std;
// Function prototypes
/* The function instruct describes the use and purpose of the program. */
void instruct();
/* The function buildList reads the file and assigns the values to an array. */
void buildList(int [], int);
/* The function caller prompts the user for a number */
int caller();
/* The function checkList checks the number input by the caller to the list. */
bool checkList(int [], int, int, int);
int binarySearch(int [], int, int, int);
/* The function displayPrize displays the prize won. */
void displayPrize(int, int, int);
/* The function sortList sorts the array using selection sort. */
void sortList (int[], int);
/* The function printList prints the array. */
void printList(int [], int);
const int LIST_SIZE = 20; //a constant integer listSize initialized 20
int main() {
// declare variables
/* an integer array prizeNumbers of size LIST_SIZE,
an integer guess intialized to 1 to hold the user's guess,
an integer variable numberGuesses initialized to 0 to count the number of
guesses made, and
a Boolean variable found initialized to false to determine if the number
is found on the list.
*/
int prizeNumbers[LIST_SIZE], guess = 1, numberGuesses = 0, guess2;
bool found = false;
int foundPos = -1;
// Calls the function instruct
instruct();
// Calls the function buildList
buildList(prizeNumbers, LIST_SIZE);
// Prints the array before sort
cout << " ***** Before sort **** ";
printList(prizeNumbers, LIST_SIZE);
// Sorts the list in ascending order
sortList(prizeNumbers, LIST_SIZE);
cout << " ***** After **** ";
// Prints the array after sort
printList(prizeNumbers, LIST_SIZE);
cout << endl;
/* loop until a guess matches the list or the user enters -1 */
while (!found && guess > 0)
{
// increment the number of guesses
numberGuesses++;
/* assign to guess the value returned from the function caller */
guess = caller();
/* if guess is greater than 0, call the function checkList */
if (guess > 0)
foundPos = binarySearch(prizeNumbers,0,LIST_SIZE - 1, guess);
if (foundPos != -1)
{
found = true;
displayPrize(numberGuesses, foundPos, guess);
}
else
cout << guess << " is not in the list. Call again. ";
}
system("pause");
return 0;
}
/* The function instruct describes the use and purpose of the program. */
void instruct()
{
cout << "This program simulates a radio station "
<< "that asks the caller to guess a number. "
<< "The number is compared against a list of "
<< "20 numbers between 1 and 500 inclusive. "
<< "The contest is held until a number has been "
<< "matched or a value of -1 is entered. A "
<< "message is displayed containing the winning "
<< "number, the location in the list of numbers, "
<< "the number of calls made, and the amount of "
<< "the prize. ";
}
/* The function buildList reads the file and assigns the values to an array. */
void buildList(int prizeNumbers[], int listSize)
{
// ****** your code for build the list into an array goes here *****
/* define an ifstream variable inData to read in the list of numbers */
// open the file
// check to see if the file opened
/* loop until all values in the list have been read */
// close the data file
int count = 0; // Loop counter variable
ifstream inputFile; // Input file stream object
inputFile.open("PrizeList.txt"); // Opens the file
while (count < listSize && inputFile >> prizeNumbers[count]) // Read the numbers from the file into the array
count++;
inputFile.close(); // Close the file
}
/* The function caller prompts the user for a number */
int caller()
{
// declare variables
int guess; // An integer guess to enter the user's guess
cout << "Hello Caller. What number between 1 and 500 are you guessing? "; // Prompt the caller to enter a value
cin >> guess; // Enter the value
if (guess == -1) // Checks to see if the user entered -1 to quit
return guess; // Returns user's guess
if (guess < 1 || guess > 500) // Checks to see if the guess is within bounds
cout << "Your guess must be between 1 and 500 inclusively. "; // Tells user the value is out of bounds
return guess; // Returns user's guess
}
/* The function checkList checks the number input by the caller to the list.
The function returns either a True (when the guess is correct) or a False
(when the guess is not in the list).
*/
int binarySearch(int anyArray[], int first, int last, int guess)
{
// declare variables
/* a Boolean variable named found initialized to false to control the loop */
int index, comparisons;
if (first > last)
index = -1;
else
{
int mid = (first + last)/2;
if (guess == anyArray[mid])
index = mid;
else
if (guess < anyArray[mid])
index = binarySearch(anyArray, first, mid-1, guess);
else
index = binarySearch(anyArray, mid+1, last, guess);
} // end if
return index;
}
/* The function displayPrize displays the prize won. */
void displayPrize(int numberGuesses, int location, int guess)
{
cout << " Caller. Your number " << guess
<< " was found at location " << location
<< " of the list Counting you, there were "
<< numberGuesses << " callers. "
<< "Your winnings are $10,000. ";
}
/* The function sortList sorts the array using selection sort. */
void sortList(int anyArray[], int len)
{
// ****** your code for sorting the array goes here *****
int i, j;
int smallestIndex;
int temp;
for (i = 0; i < len - 1; i++)
{
smallestIndex = i;
for (j = i + 1; j < len; j++)
if (anyArray[j] < anyArray[smallestIndex])
smallestIndex = j;
temp = anyArray[smallestIndex];
anyArray[smallestIndex] = anyArray[i];
anyArray[i] = temp;
}
}
/* The function printList prints the array. */
void printList(int anyArray[], int len)
{
for (int i = 0; i < len; i++)
cout << anyArray[i] << " ";
cout << endl;
}
//PrizeList.txt
42
468
335
1
170
225
479
359
463
465
206
146
282
329
462
492
496
443
328
437
Explanation / Answer
NOTE: I have changed the binary function from a recursive one to iterative. If recursion is necessary please leave in comments I will change it to a recursive one. Please give this answer a thumbs up.
OUTPUT of the code below:
This program simulates a radio station that asks the caller to guess a number.
The number is compared against a list of 20 numbers between 1 and 500 inclusive.
The contest is held until a number has been matched or a value of -1 is entered.
A message is displayed containing the winning number, the location in the list
of numbers, the number of calls made, and the amount of the prize.
***** Before sort ****
0 0 65535 1 1191775696 32767 4199262 0 2 0 4199341 0 0 16711680 0 0 4199264 0 4197376 0
***** After ****
0 0 0 0 0 0 0 0 0 0 1 2 32767 65535 4197376 4199262 4199264 4199341 16711680 1191775696
Hello Caller. What number between 1 and 500 are you guessing? Your guess must be between 1 and 500 inclusively.
**** 3 Comparisons from BinarySeach ****
Caller. Your number 4199341 was found at location 17 of the list
Counting you, there were 1 callers. Your winnings are $10,000.
CODE:
#include <iostream>
#include <fstream>
using namespace std;
//int global_count = 0;
// Function prototypes
/* The function instruct describes the use and purpose of the program. */
void instruct();
/* The function buildList reads the file and assigns the values to an array. */
void buildList(int [], int);
/* The function caller prompts the user for a number */
int caller();
/* The function checkList checks the number input by the caller to the list. */
bool checkList(int [], int, int, int);
int binarySearch(int [], int, int, int);
/* The function displayPrize displays the prize won. */
void displayPrize(int, int, int);
/* The function sortList sorts the array using selection sort. */
void sortList (int[], int);
/* The function printList prints the array. */
void printList(int [], int);
const int LIST_SIZE = 20; //a constant integer listSize initialized 20
int main() {
// declare variables
/* an integer array prizeNumbers of size LIST_SIZE,
an integer guess intialized to 1 to hold the user's guess,
an integer variable numberGuesses initialized to 0 to count the number of
guesses made, and
a Boolean variable found initialized to false to determine if the number
is found on the list.
*/
int prizeNumbers[LIST_SIZE], guess = 1, numberGuesses = 0, guess2;
bool found = false;
int foundPos = -1;
// Calls the function instruct
instruct();
// Calls the function buildList
buildList(prizeNumbers, LIST_SIZE);
// Prints the array before sort
cout << " ***** Before sort **** ";
printList(prizeNumbers, LIST_SIZE);
// Sorts the list in ascending order
sortList(prizeNumbers, LIST_SIZE);
cout << " ***** After **** ";
// Prints the array after sort
printList(prizeNumbers, LIST_SIZE);
cout << endl;
/* loop until a guess matches the list or the user enters -1 */
while (!found && guess > 0)
{
// increment the number of guesses
numberGuesses++;
/* assign to guess the value returned from the function caller */
guess = caller();
/* if guess is greater than 0, call the function checkList */
if (guess > 0)
foundPos = binarySearch(prizeNumbers,0,LIST_SIZE - 1, guess);
if (foundPos != -1)
{
found = true;
displayPrize(numberGuesses, foundPos, guess);
}
else
cout << guess << " is not in the list. Call again. ";
}
//system("pause");
return 0;
}
/* The function instruct describes the use and purpose of the program. */
void instruct()
{
cout << "This program simulates a radio station "
<< "that asks the caller to guess a number. "
<< "The number is compared against a list of "
<< "20 numbers between 1 and 500 inclusive. "
<< "The contest is held until a number has been "
<< "matched or a value of -1 is entered. A "
<< "message is displayed containing the winning "
<< "number, the location in the list of numbers, "
<< "the number of calls made, and the amount of "
<< "the prize. ";
}
/* The function buildList reads the file and assigns the values to an array. */
void buildList(int prizeNumbers[], int listSize)
{
// ****** your code for build the list into an array goes here *****
/* define an ifstream variable inData to read in the list of numbers */
// open the file
// check to see if the file opened
/* loop until all values in the list have been read */
// close the data file
int count = 0; // Loop counter variable
ifstream inputFile; // Input file stream object
inputFile.open("PrizeList.txt"); // Opens the file
while (count < listSize && inputFile >> prizeNumbers[count]) // Read the numbers from the file into the array
count++;
inputFile.close(); // Close the file
}
/* The function caller prompts the user for a number */
int caller()
{
// declare variables
int guess; // An integer guess to enter the user's guess
cout << "Hello Caller. What number between 1 and 500 are you guessing? "; // Prompt the caller to enter a value
cin >> guess; // Enter the value
if (guess == -1) // Checks to see if the user entered -1 to quit
return guess; // Returns user's guess
if (guess < 1 || guess > 500) // Checks to see if the guess is within bounds
cout << "Your guess must be between 1 and 500 inclusively. "; // Tells user the value is out of bounds
return guess; // Returns user's guess
}
/* The function checkList checks the number input by the caller to the list.
The function returns either a True (when the guess is correct) or a False
(when the guess is not in the list).
*/
int binarySearch(int arr[], int l, int r, int x)
{
int count = 0, m;
while (l <= r)
{
m = l + (r-l)/2;
// Check if x is present at mid
if (arr[m] == x)
{
count++;
break;
}
// If x greater, ignore left half
if (arr[m] < x)
{
count++;
l = m + 1;
}
// If x is smaller, ignore right half
else
{
count++;
r = m - 1;
}
}
if (arr[m] == x)
{
cout<<" **** "<< count <<" Comparisons from BinarySeach **** ";
return m;
}
// if we reach here, then element was
// not present
return -1;
}
/* The function displayPrize displays the prize won. */
void displayPrize(int numberGuesses, int location, int guess)
{
cout << " Caller. Your number " << guess
<< " was found at location " << location
<< " of the list Counting you, there were "
<< numberGuesses << " callers. "
<< "Your winnings are $10,000. ";
}
/* The function sortList sorts the array using selection sort. */
void sortList(int anyArray[], int len)
{
// ****** your code for sorting the array goes here *****
int i, j;
int smallestIndex;
int temp;
for (i = 0; i < len - 1; i++)
{
smallestIndex = i;
for (j = i + 1; j < len; j++)
if (anyArray[j] < anyArray[smallestIndex])
smallestIndex = j;
temp = anyArray[smallestIndex];
anyArray[smallestIndex] = anyArray[i];
anyArray[i] = temp;
}
}
/* The function printList prints the array. */
void printList(int anyArray[], int len)
{
for (int i = 0; i < len; i++)
cout << anyArray[i] << " ";
cout << endl;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.