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;
}

Edited 5 Years Ago by mpassaglia: n/a

In your search function, counter should be a reference, not a pointer. So you should delete the * on line 17, and in line 98, you should change "int * counter" to "int & counter".

In your search function, counter should be a reference, not a pointer. So you should delete the * on line 17, and in line 98, you should change "int * counter" to "int & counter".

Perfect, the logic behind that makes a lot more sense than what my friends had told me to try. Just had to also change the function prototype to search(int*,int,int&)

thanks!

This question has already been answered. Start a new discussion instead.