#include <iostream>
#include <cstdlib>
using namespace std;
// callback for qsort and bsearch
int comp( const void*, const void* ); 
unsigned promptAndRead( char prompt[ ] );
unsigned* allocate( unsigned );
void fillVector( unsigned*, unsigned, unsigned );

int main() {
   unsigned* nums; // vector of random integers
   int n;          // its size
   unsigned* keysNotFound; // vector of keys not in nums
   int m;                  // its size
   unsigned range; // of integers in vectors
   int i, j;

   // Prompt for vector size.
   n = promptAndRead( "Vector size? " );
   // Prompt user for range of random numbers as
   // an integer multiple of array size (e.g., if array
   // size is 100, range could be 100 * 2, 100 * 3,
   // 100 * 4, etc.).
   range = promptAndRead( "Multiplier for range (>= 2)? " );
   range *= n;
   range++;
   // Prompt for size of vector of keys not found in nums.
   m = promptAndRead( "Keys-not-found size? " );
   
   // Allocate heap storage for the vector, 
   nums = allocate( n );
   keysNotFound = allocate( m );
   
   // Fill array with random numbers.
   fillVector( nums, n, range );
   
   // Sort it using library function qsort.
   qsort( nums,                 // vector to sort
          n,                    // its size
          sizeof( nums[ 0 ] ),  // element size in bytes
          comp );               // comparison function

   // Print sorted array.
   for ( i = 0; i < n; i++ )
      cout << nums[ i ] << endl;

   // Generate random numbers as keys to be 
   // searched for in the array, halting when
   // m such keys are not in the array. Save
   // these keys into an array of their own for
   // later printing. Library function bsearch used
   // for searching.
   unsigned key, count = 0;        
   j = 0; // index into keysNotFound
   do {
      key = rand() % range; // generate random key
      count++;              // count it
      // if key not in vector, add it to keysNotFound
      if ( !bsearch( &key,                // key's address
                     nums,                // search vector
                     n,                   // its size
                     sizeof( nums[ 0 ] ), // element size 
                     comp ) )             // callback
        keysNotFound[ j++ ] = key; // add it to vector
   } while ( j < m );
             
   // Print keys not found in array, after sorting.
   qsort( keysNotFound, m, sizeof( *keysNotFound ), comp );
   cout << "\n**** " << count 
        << " tries to find " << m
        << " keys not in the array." << endl;
   for ( j = 0; j < m; j++ )
      cout << keysNotFound[ j ] << endl;
   return 0;
}

// qsort and bsearch callback: 
// returns one of three integer values:
//    < 0 means that *p1 < *p2
//    > 0 means that *p1 > *p2
//      0 means that *p1 == *p2
int comp( const void* p1, const void* p2 ) {
   return *static_cast<const unsigned*>(p1) - 
          *static_cast<const unsigned*>(p2);
}

// Prompts user for size of arrays and for range.
unsigned promptAndRead( char prompt[ ] ) {
   int temp;
   // Prompt user for vector size.
   do {
     cout << prompt;
     cin >> temp;
   } while ( temp <= 0 );
   return temp;
}

unsigned* allocate( unsigned n ) {
   return new unsigned[ n ];
}

void fillVector( unsigned* v, unsigned n, unsigned r ) {
   for ( unsigned i = 0; i < n; i++ ) 
     v[ i ] = rand() % r;
}