/*
 **************************************************************************
 * Program name : 043_Binary_search (Version 1.00)                        *
 * Author       : Duck Wong                                               *
 * Language     : C / C++                                                 *
 * Compiler     : Boodshed Dec-C++ compiler Ver 3.95                      *
 * Computer     : PII350                                                  *
 * O/S          : Windows 98                                              *
 **************************************************************************
 * Version 1.00 : 2000/06/26 - first version                              *
 **************************************************************************
 * Description  : (a) Generate a list of integer numbers                  *
 *                (b) Input an integer number                             *
 *                (c) Sort the elements in the array and display them     *
 *                (d) Is the inputted number in the array ?               *
 *                (e) Try again ?                                         *
 **************************************************************************
*/
#include <iostream.h>
#include <stdlib.h>
#include <iomanip.h>
#include <time.h>

const int Arraysize = 15;
int   Intarray[Arraysize];

void  getnumbers(int Intarray[])                                     // Note (1)
{
 int Index_1, Index_2;

 for (Index_1=0; Index_1<Arraysize; Index_1++)
   {
    Intarray[Index_1] = rand() % 50 + 1;
    if (Index_1>0)
      for (Index_2=0; Index_2<Index_1; Index_2++)
        if (Intarray[Index_1]==Intarray[Index_2])
          {
           Index_1--;
           break;
          }
   }
}

void  sortnumber(int Intarray[])                                     // Note (2)
{
 int Index_1, Index_2, tempint;

 for (Index_1=0; Index_1<Arraysize-1; Index_1++)
   for (Index_2=Index_1+1; Index_2<Arraysize; Index_2++)
     if (Intarray[Index_1]>Intarray[Index_2])
       {
        tempint = Intarray[Index_1];
        Intarray[Index_1] = Intarray[Index_2];
        Intarray[Index_2] = tempint;
       }
}

void searchnumber(int Intarray[], int Yournumber)                    // Note (3)
{
 int  Index;
 int  First;           // THE FIRST ELEMENT UNDER CONSIDERATION
 int  Last;            // THE LAST ELEMENT UNDER CONSIDERATION
 int  Mid;             // THE ELEMENT IN THE MIDDLE OF THE LIST
 int  Pass;            // NUMBER OF PASS WHILE RUNNING THE BINARY SEARCH
 char Found;

 First = 1;
 Last  = Arraysize;
 Found = 'N';
 Pass  = 0;
 // The following line is added to show the status of each pass.
 cout << "\n\n\tPass:  First:  Last:  Mid:  That is:  Target:  Result:";
 do {
     Pass++;
     Mid =(First+Last) / 2;
     // The following lines are added to show the status of each pass.
     cout << "\n\t  " << Pass
          << setw(7) << First
          << setw(8) << Last
          << setw(6) << Mid
          << setw(9) << Intarray[Mid-1]
          << setw(9) << Yournumber;
     if (Intarray[Mid-1] < Yournumber)
       cout << "     Smaller than targer";
     else
       {
        if (Intarray[Mid-1] > Yournumber)
          cout << "     Bigger than targer";
        else
          cout << "     Same as targer";
       }
     // The above lines are added to show the status of each pass.
     if (Intarray[Mid-1] < Yournumber)
       First = Mid+1;
     else
       if (Intarray[Mid-1] > Yournumber)
          Last = Mid-1;
        else Found = 'Y';
    } while ((First<=Last) && (Found=='N'));
 if (Found=='Y') cout << "\n\n\tThat's great! Your number is in the list.";
 else cout << "\n\n\tSorry your number is not in the list.";
}

int main()
{
 // part 1 : declaration
 int   Index;                        // loop counter
 int   Yournumber;                   // Inputted by the user.
 const int Arraysize=15;             // Maximum no. of element 15
 int   Intarray[Arraysize];          // Define the array Number
 char  Again;                        // Try again ?

 do {
     srand(time(NULL));
     // part 2 : Generate a list of integer numbers
     getnumbers(Intarray);

     // part 3 : Input an integer number
     cout << "\n\tThere are 15 integer numbers selected from 1 to 50."
          << "\n\tPlease enter any number within 1 to 50, then this program"
          << "\n\twill compare your number with these selected numbers.\n";
     do {
         cout << "\n\t\tYour number is : ";
         cin  >> Yournumber;
        } while ((Yournumber<1) || (Yournumber>50));

     // part 4 : Sort the elements in the array and display them
     cout << "\n\tThe sorted list is : \n\t";
     sortnumber(Intarray);
     for (Index=0; Index<Arraysize; Index++)
       {
        cout << Intarray[Index];
        if (Index<(Arraysize-1)) cout << ", ";
       }

     // part 5 : Is the inputted number in the array ?
     searchnumber(Intarray, Yournumber);

     // part 6 : try another number ?
     cout << "\n\n\t\aTry another number (Y/N) : ";
     cin  >> Again;
     cout << "\n";
    }while (Again=='Y' || Again=='y');
 cout << "\n" << endl;

 system("PAUSE");
 return 0;
}

/* Note
   (1) Generates a list of integer numbers and stores these numbers in an array.
   (2) Sort the elements in the array
   (3) Use Binary search method to seek the inpuuted number in the array.

       Example :

        The sorted list is :
        3, 15, 17, 19, 24, 25, 27, 36, 40, 41, 42, 44, 45, 48, 50

        Pass:  First:  Last:  Mid:  That is:  Target:  Result:
          1      1      15     8       36       15     Bigger than targer
          2      1       7     4       19       15     Bigger than targer
          3      1       3     2       15       15     Same as targer

        That's great! Your number is in the list.
*/