Pr8-2 // This program demonstrates the binarySearch function, which performs a binary search on an integer array

// Pr8-2
// This program demonstrates the binarySearch function, which
// performs a binary search on an integer array.
#include <iostream>
using namespace std;

// Function prototype
int binarySearch(const int [], int, int);
const int SIZE = 20;

int main()
{
   // Array with employee IDs sorted in ascending order.
   int idNums[SIZE] = {101, 142, 147, 189, 199, 207, 222,
                       234, 289, 296, 310, 319, 388, 394,
                       417, 429, 447, 521, 536, 600};
   int results;   // To hold the search results
   int empID;     // To hold an employee ID
 
   // Get an employee ID to search for.
   cout << "Enter the employee ID you wish to search for: ";
   cin >> empID;
 
   // Search for the ID.
   results = binarySearch(idNums, SIZE, empID);
 
   // If results contains -1 the ID was not found.
   if (results == -1)
      cout << "That number does not exist in the array.\n";
   else
   {
      // Otherwise results contains the subscript of
      // the specified employee ID in the array.
      cout << "That ID is found at element " << results;
      cout << " in the array.\n";
   }
   return 0;
}

//***************************************************************
// The binarySearch function performs a binary search on an     *
// integer array. array, which has a maximum of size elements,  *
// is searched for the number stored in value. If the number is *
// found, its array subscript is returned. Otherwise, -1 is     *
// returned indicating the value was not in the array.          *
//***************************************************************

int binarySearch(const int array[], int size, int value)
{
   int first = 0,             // First array element
       last = size - 1,       // Last array element
       middle,                // Mid point of search
       position = -1;         // Position of search value
   bool found = false;        // Flag

   while (!found && first <= last)
   {
      middle = (first + last) / 2;     // Calculate mid point
      if (array[middle] == value)      // If value is found at mid
      {
         found = true;
         position = middle;
      }
      else if (array[middle] > value)  // If value is in lower half
         last = middle - 1;
      else
         first = middle + 1;           // If value is in upper half
   }
   return position;
}