Homework 8  (Due Nov. 25 in class)

Read: Section 4.2, 4.3, 4.4, 4.5, 4.6, 4.7, 4.8, 4.9;
                 Pay special attention on 4.2, 4.3, 4.4, 4.6, 4.8, 4.9;
                 Compile and run the 19 examples in Chapter 4.

(Problem 1),  (10 pts)
Run fig04_19.cpp on page 269 and then:
(1) Use rand() to generate 100 random numbers, then place the random number to the array.
(2)  Increase the array size as large as possible until your computer can't handle it.
   Hand in the version you modified, which meets the following two conditions:
   (a) The array size is almost reach the limit. (b) It still works on the PC in the Lab.

(Problem 2),  (10 pts)
Run fig04_20.cpp on page 271 and then:
(1) Use rand() to generate 15 random numbers (between 1 -100),  place the random number to an array.
(2) Use hw-4-11(a) to sort the 15 random numbers, and then search a number.

(Problem 3), 4-33, on page 303. (10 pts)
A suggested solution is posted below    Your job is to decrease the array size to 50, then use
rand() to generate 50 random numbers, then place the random number to the array.  And then
do the linear search.

(Problem 4), 4-34, on page 303. (10 pts)
A suggested solution is posted below    Your job is to increase the array size to 50, then use
rand() to generate 50 random numbers, then place the random number to the array.  And then
use hw-4-11(a) to sort the 50 random numbers, And then do the Binary search.

using std::cout;
using std::endl;
using std::cin;

int linearSearch( const int [], int, int, int );

int main()
{
   const int SIZE = 100;
   int array[ SIZE ], searchKey, element;

   for ( int loop = 0; loop < SIZE; ++loop )
      array[ loop ] = 2 * loop;

   cout << "Enter the integer search key: ";
   cin >> searchKey;

   element = linearSearch( array, searchKey, 0, SIZE - 1 );

   if ( element != -1 )
      cout << "Found value in element " << element << endl;
   else
      cout << "Value not found" << endl;

   return 0;
}

int linearSearch( const int array[], int key, int low, int high )
{
   if ( array[low] == key )
      return low;
   else if ( low == high )
      return -1;
   else
      return linearSearch( array, key, low + 1, high );
}

// Exercise 4.34 Solution
#include <iostream>

using std::cout;
using std::endl;
using std::cin;

#include <iomanip>

using std::setw;

const int SIZE = 15;

int binarySearch( const int [], int, int, int );
void printRow( const int [], int, int, int );
void printHeader( void );

int main()
{
   int a[ SIZE ], key, result;

   for ( int i = 0; i < SIZE; ++i )
      a[ i ] = 2 * i;

   cout << "Enter a number between 0 and 28: ";
   cin >> key;

   printHeader();
   result = binarySearch( a, key, 0, SIZE - 1 );

   if ( result != -1 )
      cout << '\n' << key << " found in array element " << result << endl;
   else
      cout << '\n' << key << " not found" << endl;

   return 0;
}

int binarySearch( const int b[], int searchKey, int low, int high )
{
   int middle;

   if ( low <= high ) {
      middle = ( low + high ) / 2;
      printRow( b, low, middle, high );

      if ( searchKey == b[ middle ] )
         return middle;
      else if ( searchKey < b[ middle ] )
         return binarySearch( b, searchKey, low, middle - 1 );
      else
         return binarySearch( b, searchKey, middle + 1, high );
   }

   return -1;   // searchKey not found
}

// Print a header for the output
void printHeader( void )
{
   cout << "Subscripts:\n";

   for ( int i = 0; i < SIZE; ++i )
      cout << setw( 3 ) << i << ' ';

   cout << '\n';

   for ( int k = 1; k <= 4 * SIZE; ++k )
      cout << '-';

   cout << '\n';
}

// print one row of output showing the current
// part of the array being processed.
void printRow( const int b[], int low, int mid, int high )
{
   for ( int i = 0; i < SIZE; ++i )
      if ( i < low || i > high )
         cout << "    ";
      else if ( i == mid )
         cout << setw( 3 ) << b[ i ] << '*';    // mark middle value
      else
         cout << setw( 3 ) << b[ i ] << ' ';

   cout << '\n';
}