Hello DaniWeb!
I've been struggling with a small detail of this program for a few days now, and haven't come up with any solutions on my own. The basic gist of the assignment is to fill an array with random numbers, sort it, and then search for a number in the array using a binary search. The program should then output whether or not the number was found and, if so, how many times the binary search function performed a comparison.
I keep coming up with either 0 comparisons, or a memory leak. Help plz?
Edit: the search and sort have to be functions, and all I/O must be done through main
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#define n 10
using namespace std;
void generateRand(int*);
void sort(int*, int);
int search(int*, int, int*);
int main()
{
int key, // number the user would like to search for
x, // for loop counter
* counter = 0, // number of times user searches for random
* ptr = new int[n], // pointer to an integer array
search_result; // stores value of search result
generateRand(ptr);
sort(ptr, n);
for(x = 0; x < n; x++)
cout << *(ptr+x) << endl;
cout << "Enter a number between 1 and 100 to search for: ";
cin >> key;
search_result = search(ptr, key, counter);
if (search_result != -1)
{
cout << key << " was found in the array after "
<< counter << " comparisons." << endl << endl;
}
else
cout << "Search key not found!" << endl << endl;
delete[] ptr;
ptr = NULL;
system("PAUSE");
return 0;
}
/*
Function Description - Generates random numbers into an array that is passed
Input - pointer
*/
void generateRand(int * ptr)
{
int x;
srand( time(NULL));
for(x = 0; x < n; x++)
*(ptr+x) = 1 + rand() % 100;
}
/*
Function Description - Sorts an array of randomly generated numbers in
ascending order
Input - pointer, int
*/
void sort(int * ptr, int size)
{
int start,
index,
minIndex,
minValue;
for (start = 0; start < size - 1; start++)
{
minIndex = start;
minValue = *(ptr+start);
for (index = start + 1; index < size; index++)
{
if (*(ptr+index) < minValue)
{
minValue = *(ptr+index);
minIndex = index;
}
}
*(ptr+minIndex) = *(ptr+start);
*(ptr+start) = minValue;
}
}
/*
Function Description - Searches an array for a value using a binary search
Input - pointer, int, int
Output - int
*/
int search(int * ptr, int value, int * counter)
{
int first = 0,
last = n - 1,
middle,
position = -1,
x;
bool found = false;
while (!found && first <= last)
{
middle = (first + last) / 2;
if (*(ptr+middle) == value)
{
found = true;
position = middle;
}
else if (*(ptr+middle) > value)
last = middle-1;
else
first = middle + 1;
counter++;
}
return position;
}