program that compares linear and binary searches

[june89]

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.
}
//Report the number of comparisons when number is not found.
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]

[jonnin]

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.

[keskiverto]

Please use code tags when posting code. See http://www.cplusplus.com/articles/jEywvCM9/