### program that compares linear and binary searches

I am trying to change the code from searches that return an array position to searches that count the number of comparisons. What should I return from the linear search? What is keeping the program from calling or completing the second binary search?
/*Ch8Ex8
June Stine
This program performs a linear search and a binary search on an array with 20 values.
Each search tracks and displays the number of comparisons made and the results.
*/

#include <iostream>
using namespace std;

//Function prototype
void searchList(const int[], const int, int);
int binarySearch(const int[], const int, int);

const int ARRAY_SIZE = 20;

int main()
{
const int tests[ARRAY_SIZE] = { 101,142,147,189,199,207,222,234,289,296,310,
319,388,394,417,429,447,521,536,600 };
int number;

//Print my name as the first line of output.
cout << "June Stine" << endl;

//Prompt the user to enter a number to search for.
cout << "Enter the number you are looking for: "<< endl;
cin >> number;

//Validate the number entered.
while (number <= 100 && number > 600)
{
cout << "That number is not within the range of tests. Please enter a number between 100 and 600." << endl;
cin >> number;
}

//Perform a linear search on the array for the number.
searchList(tests, ARRAY_SIZE, number);

bool found = false;

//Perform a binary search on the array for the number.
binarySearch(tests, ARRAY_SIZE, number);

//Keep the console window open until the enter key is pressed.
cout << "Press the enter key to exit.";
cin.ignore(cin.rdbuf()->in_avail() + 1);

return 0;
}

//Function Definition to perform a linear search for the user number.
void searchList(const int tests[], const int AARAY_SIZE, int number)
{
int count = 0;//Initialize variable for reporting the number of comparisons.
bool found = false;//Initialize the flag to indicate the number is not yet found.

while (count < (AARAY_SIZE - 1) && !found)//Define conditions for running the if comparison.
{
if (tests[count] == number)//Compare each array element with the the user number.
{
found = true;//Set flag to show the number was found.
//Display the results of search.
cout << "After " << (count + 1) << " comparisons, The linear search found number " << number << "." << endl;
}
count++;//Increment the count for each comparison.
}
if (found == false)
cout << "After " << (count + 1) << " comparisons, the linear search did not find number " << number << "." << endl;
}

//Function Definition to perform a binary search for the user number.
int binarySearch(const int tests[], const int AARAY_SIZE, int number)
{
int first = 0, last = (ARRAY_SIZE - 1), middle;//Define variables to limit the range of the array size to search.
bool found = false;//Set the flag to show the number is not yet found.
int comparisons= 0;//Initialize a variable for the accumulating the number of comparisons.

while (!found && first <= last);//Set the conditions for continuing the binary search.
{
middle = (first + last) / 2.0;//Calculate the middle of the array.

if (tests[middle] == number)//Compare the middle element with the user number.
found = true;//Set the flag when the number is found.

else if (tests[middle] > number)//Set conditions for changing the value of the last element to search.
last = middle - 1;

else//Set conditions for changing the value of the first element to search.
first = middle + 1;
comparisons++;//Increment the accumulator for each comparison.
}

//Display the results for the search.
if (found = true)
cout << "After " << comparisons << "comparisons, the binary search found the number " << number << "." << endl;
else
cout << "After " << comparisons << "comparisons, The binary search did not find the number " << number << "." << endl;

return comparisons;
}

[Enter the number you are looking for:
521
After 18 comparisons, The linear search found number 521.
/code]
linear search is pretty simple: for(blah) did you find it? If yes, you looked #for loop variable# number of times (possibly off by one depending but you can figure it out and correct it). If you don't find it, it should have looked N times where N is number of things in the list. 18 looks correct to me for 521.

I don't see the issue with the binary search yet. Remember that you must sort a list to binary search it, else it will fail, and IMHO the effort to sort counts against the search, at least for the first one. If you search the list a bunch, the sort effort goes to zero the more searches you do. If the data is already sorted, that works too, but it isn't always.
Last edited on
Please use code tags when posting code. See http://www.cplusplus.com/articles/jEywvCM9/