using c++

Here, you will need to modify the functions binary() and linear() to count the number of comparisons that are performed to find the target number.

Next, you will need to modify computeAverageLinear() and computeAverageBinary() to determine the number of compares on average it takes to find each element in the array.

Example

Consider the file numbers.txt that has the following values:

1 4 10 36 47 92 100 110 125 136 142 143 150 160 167

For the above example, the list is:

0	1	2	3	4	5	6	7	8	9	0	11	12	13	14
1	4	10	36	47	92	100	110	125	136	142	143	150	160	167

When we run the program on the above list, the program will compute how long it takes to find an element in the list using the linear search method and using the binary search method. If I call linear() (a function performing a linear search from left to right) with the search parameter set to 4, then I will find it with two comparisons. This means linear(list, num, 4) == 2 because the function linear() will return the number of comparisions, list contains the list of numbers, and num is the number of items in list. Thus linear(list, num, 47) == 5. To find the average cost of the linear search, the equation will be:

(linear(list, num, 1) + linear(list, num, 4) + + linear(list, num, 167))/num == (1 + 2 + ... + 15) / 15 == 120 / 15 == 8.0

To compute the average cost of the binary search, the equation will be:

(binary(list, num, 1) + binary(list, num, 4) + + binary(list, num, 167))/num == 3.3

The user input is underlined.

Enter filename of list: numbers.txt Linear search: 8.0 Binary search: 3.3 

code below:

#include #include #include using namespace std;

int readNumbers(int list[], int max); float computeAverageLinear(int list[], int num); float computeAverageBinary(int list[], int num); int linear(int list[], int num, int search); int binary(int list[], int num, int search)

int main() { int list[1024]; const int MAX = sizeof (list) / sizeof (list[0]); int num;

// read the numbers if (!(num = readNumbers(list, MAX))) return 1;

// determine how long it takes for a linear search float averageLinear; averageLinear = computeAverageLinear(list, num);

// determine how long it takes for a binary search float averageBinary; averageBinary = computeAverageBinary(list, num);

// display results cout.setf(ios::fixed); cout.setf(ios::showpoint); cout.precision(1); cout << "Linear search: " << setw(10) << averageLinear << endl; cout << "Binary search: " << setw(10) << averageBinary << endl;

return 0; }

/************************************************************ * READ NUMBERS * Input: * list: a list of numbers to search through * max: the size of the numbers list * Output: * num: the number of items actually read ***********************************************************/ int readNumbers(int list[], int max) { char fileName[256]; int num = 0;

// get the filename cout << "Enter filename of list: "; cin >> fileName;

// open the file ifstream fin(fileName); if (fin.fail()) { cout << "Unable to open file " << fileName << endl; return 0; }

// read the file while (num < max && fin >> list[num]) num++;

// make like a tree fin.close(); return num; }

/********************************************************* * COMPUTE AVERAGE LINEAR * Input: * list: a list of numbers to search through * num: the size of the numbers list * Output: * averageLinear: the average number of comparisons it takes * to find each item in the array *******************************************************/ float computeAverageLinear(int list[], int num) {

float averageLinear = 0.0;

// put your code here, probably including a collections of // calls to linear()

return averageLinear; }

/********************************************************* * COMPUTE AVERAGE BINARY * Input: * list: a list of numbers to search through * num: the size of the numbers list * Output: * averageBinary: the average number of comparisons it takes * to find each item in the array *******************************************************/ float computeAverageBinary(int list[], int num) { float averageBinary = 0.0;

// put your code here, probably including a collections of // calls to binary()

return averageBinary; }

/******************************************************* * LINEAR * Input: * list: a list of numbers to search through * num: the size of the numbers list * search: the number that you are searching for * Output: * compares: the number of compares that were made * before 'search' was found in the 'numbers' array ******************************************************/ int linear(int list[], int num, int search) { bool found = false; int compares = 0; // you will need to compute this

for (int i = 0; i < num && ! found; i++) if (search == list[i]) found = true;

return compares; }

/******************************************************* * BINARY * Input: * list: a list of numbers to search through * num: the size of the numbers list * search: the number that you are searching for * Output: * compares: the number of compares that were made * before 'search' was found in the 'numbers' array ******************************************************/ int binary(int list[], int num, int search) { bool found = false; int compares = 0; // you will need to compute this

// set the bounds of the search space, initially the whole list int iFirst = 0; int iLast = num - 1;

// continue until found or the search size is not zero while (iLast >= iFirst && !found) { int iMiddle = (iLast + iFirst) / 2;

// note that both the == and > count as one comparison if (list[iMiddle] == search) found = true; else if (list[iMiddle] > search) iLast = iMiddle - 1; else iFirst = iMiddle + 1; }

return compares; }