I need help with this c++ homework question. I saw some other person already ask
ID: 3555349 • Letter: I
Question
I need help with this c++ homework question. I saw some other person already asked this question, but the answer had some odd coding that I didn't quite understand. Any help is much appreciated.
Exercise 1: The variable middle is defined as an integer. The program contains the assignment statement middle=first + (last-first)/2. Is the right side of this statement necessarily an integer in computer memory? Explain how the middle value is determined by the computer. How does this line of code affect the logic of the program? Remember that first, last, and middle refer to the array positions, not the values stored in those array positions.
Exercise 2: Search the array in the program above for 19 and then 12. Record what the output is in each case. Note that both 19 and 12 are repeated in the array. Which occurrence of 19 did the search find? Which occurrence of 12 did the search find? Explain the difference.
Exercise 3: Modify the program to search an array that is in ascending order. Make sure to alter the array initialization.
#include<iostream>
using namespace std;
int binarySearch(int [], int, int); // function prototype
const int SIZE = 16;
int main()
{
int found, value;
int array[] = {34,19,19,18,17,13,12,12,12,11,9,5,3,2,2,0}; // array to be searched
cout << "Enter an integer to search for:" << endl;
cin >> value;
found = binarySearch(array, SIZE, value); //function call to perform the binary search
//on array looking for an occurrence of value
if (found == -1)
cout << "The value " << value << " is not in the list" << endl;
else
{
cout << "The value " << value << " is in position number "
<< found + 1 << " of the list" << endl;
}
return 0;
}
//*******************************************************************
// binarySearch
//
// task: This searches an array for a particular value
// data in: List of values in an orderd array, the number of
// elements in the array, and the value searched for
// in the array
// data returned: Position in the array of the value or -1 if value
// not found
//
//*******************************************************************
int binarySearch(int array[],int numElems,int value) //function heading
{
int first = 0; // First element of list
int last = numElems - 1; // last element of the list
int middle; 0 // variable containing the current
// middle value of the list
while (first <= last)
{
middle = first + (last - first) / 2;
if (array[middle] == value)
return middle; // if value is in the middle, we are done
else if (array[middle]<value)
last = middle - 1; // toss out the second remaining half of
// the array and search the first
else
first = middle + 1; // toss out the first remaining half of
// the array and search the second
}
return -1; // indicates that value is not in the array
}
Explanation / Answer
a) The middle can be found out by either mid = (first + last)/2 or mid = first + (last-first)/2. The first case will find the mid incorrectly for values where first+last becomes greater than the max value of integer. In latter it is not the case. The searching in the latter can be done easily even for large integers.
b) For searching 19, the iterations are:
mid = 7 array[7] = 12, so search again in the first half as 12 < 19 making last = 7-1
mid = 3 array[3] = 18, so search again in the first half as 18 < 19 making last = 3-1
mid = 1 array[1] = 19, It is now found!! so return 1;
For searching 12, the iterations are:
mid = 7; array[7] = 12, It is now found!! so return 7 [Note that 12 is the second duplicate in the array] So it shows that the first value the binary search method finds gets returned.
c)
#include<iostream>
using namespace std;
int binarySearch(int [], int, int); // function prototype
const int SIZE = 16;
int main()
{
int found, value;
int array[] = {0,2,2,3,5,9,11,12,12,13,17,18,19,19,34}; // array to be searched
cout << "Enter an integer to search for:" << endl;
cin >> value;
found = binarySearch(array, SIZE, value); //function call to perform the binary search
//on array looking for an occurrence of value
if (found == -1)
cout << "The value " << value << " is not in the list" << endl;
else
{
cout << "The value " << value << " is in position number "
<< found + 1 << " of the list" << endl;
}
return 0;
}
//*******************************************************************
// binarySearch
//
// task: This searches an array for a particular value
// data in: List of values in an orderd array, the number of
// elements in the array, and the value searched for
// in the array
// data returned: Position in the array of the value or -1 if value
// not found
//
//*******************************************************************
int binarySearch(int array[],int numElems,int value) //function heading
{
int first = 0; // First element of list
int last = numElems - 1; // last element of the list
int middle; 0 // variable containing the current
// middle value of the list
while (first <= last)
{
middle = first + (last - first) / 2;
if (array[middle] == value)
return middle; // if value is in the middle, we are done
else if (array[middle]>value)
last = middle - 1; // toss out the second remaining half of
// the array and search the first
else
first = middle + 1; // toss out the first remaining half of
// the array and search the second
}
return -1; // indicates that value is not in the array
}
The above code is modified and the only change requried are marked as bold