Write a program that has an array of at least 20 integers. It should call a func
ID: 3908440 • Letter: W
Question
Write a program that has an array of at least 20 integers. It should call a function that uses the linear search algorithm to locate one of the values. 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.
I need help displaying the binaryCount function on the screen. I am unsure how to raise the binaryCount in the program.
#include <iostream>
using namespace std;
void linearSearch(int array[], int size, int searchValue)
{
int linearCount = 0;
for (int x = 0; x<size; x++)
{
linearCount++;
if (searchValue ==array[x])
{
break;
}
}
cout << endl << "Linear search comparisons: " << linearCount;
}
void binarySearch(int array[], int size, int searchValue)
{
int binaryCount = 0;
int low = 0;
int high = size - 1;
int mid;
mid = (high + low) / 2;
while (low <= high)
{
if (searchValue == array[mid])
{
break;
}
else if (searchValue > array[mid])
{
binaryCount++;
low = mid + 1;
}
else
{
binaryCount++;
high = mid - 1;
}
cout << endl << "Binary search comparisons: " << binaryCount << endl;
}
}
int main()
{
int list[] = { 1,3,7,13,14,19,22,24,29,33,35,42,53,61,64,66,67,78,81,83};
cout << "The list of data that is used for the program: ";
for (int i = 0; i<20; i++)
{
cout << list[i] << " ";
}
linearSearch(list, 20, 22);
binarySearch(list, 20, 22);
return 0;
}
Explanation / Answer
As soon as you enter the the while (low <= high) within the binarySearch function you are bound to compare the value in hand with the mid value in first if (searchValue == array[mid]), hence one binaryCount++ must be placed before that (or say after entering in while). If it goes in, you break and no problem, otherwise, you are bound to check else if (searchValue > array[mid]), hence takeout the binaryCount++ from the loop (as the comaprison may not result as TRUE, but you still performed it!) to count for this comparison. At last, if all else fails, delete the binaryCount++ inside else as, if the above two compairsons fail, you are bound to choose this and required no additional comparisons.
Hope this helps!
For you reference:
void binarySearch(int array[], int size, int searchValue)
{
int binaryCount = 0;
int low = 0;
int high = size - 1;
int mid;
mid = (high + low) / 2;
while (low <= high)
{
binaryCount++; //....................... Place one HERE!
if (searchValue == array[mid])
{
break;
}
binaryCount++; //........................ Place this HERE!
else if (searchValue > array[mid])
{
low = mid + 1;
}
else
{
// binaryCount++; ............................. REMOVE THIS
high = mid - 1;
}
cout << endl << "Binary search comparisons: " << binaryCount << endl;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.