Question
Write a program that has an array of 20 integers. Ask the user to enter the values to fill the array with. It should then
Write a program that has an array of 20 integers. Ask the user to enter the values to fill the array with. It should then prompt the user to enter a value to search four. It should call a function that uses the linear search algorithm to locate that value. The function should keep a count of the number of comparisons it makes until it finds the value. The program then should call a function that uses the binary search algorithm to locate the same value. It should also keep count of the number of comparisons it makes. Display these values on the screen. Sample output of the program is provided below. Note that your output may vary slightly depending on the implementation details of your algorithms.
//Note that the Array itself needs to be generated using RAND FUNCTION and the Limit is between -100 and 100
//C++ Programming Language Sample Input/Output Enter 20 integers: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Enter an integer to search for: 15 Number of comparisons necessary in linear search: 16 Number of comparisons necessary in binary search: 7
This is what I have for the Program so far.
#include
int LinearSearch (int[], int); int BinarySearch (int[], int);
int LinearSearch (int a[], int i) { int k = 0; for (; ((a[k] != i) && (k < 20)); k++) { } if (a[k] == i) return (k + 1); else return -1; }
int BinarySearch (int a[], int i) { int First = 0; int Last = 19; int Middle = 0; int count = 0;
do { Middle = First + ((Last - First) / 2); count++; if (a[Middle] > i) Last = Middle; else if (a[Middle] < i) First = Middle; else return count; } while (count < 20);
}
void main () { int Array[20]; int Comp = 0; int Search = 0; cout << "Enter 20 integers: " << endl; for (int i = 0; i < 20; i++) { cin >> Array[i]; }
cout << "Enter an integer to search for: "; cin >> Search;
Comp = LinearSearch (Array, 12); if (Comp > 0) cout << "Number of comparisons necessary in linear search: " << Comp << endl; else cout << "The function did not find the number searched for";
Comp = BinarySearch (Array, 12); if (Comp > 0) cout << "Number of comparisons necessary in binary search: " << Comp << endl; else cout << "The function did not find the number searched for"; }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started