// Chap 2, p 85

#include <iostream.h>

int BinSearch(const int A[], int First, int Last,
              int Value)
// ---------------------------------------------------------
// Searches the array elements A[First] through A[Last] 
// for Value by using a binary search.
// Precondition: 0 <= First, Last <= SIZE - 1, where
// SIZE is the maximum size of the array, and
// A[First] <= A[First+1] <= ... <= A[Last].
// Postcondition: If Value is in the array, returns
// the index of the array element that equals Value;
// otherwise returns -1.
// ---------------------------------------------------------
{
   if (First > Last)
      return -1;      // Value not in original array

   else
   {  // Invariant: If Value is in A, 
      //            A[First] <= Value <= A[Last]
      int Mid = (First + Last)/2;
      if (Value == A[Mid])
         return Mid;  // Value found at A[Mid]

      else if (Value < A[Mid])
         return BinSearch(A, First, Mid-1, Value);  // X

      else
         return BinSearch(A, Mid+1, Last, Value);   // Y
   }  // end else
}  // end BinSearch

// ******SAMPLE MAIN PROGRAM****** }
main()
{  const Size = 15;  // max size of array

   int A[] = {3, 5, 6, 8, 9, 11, 15, 16,
		       17, 20, 23, 25, 31, 32, 35};

   int First, Last, Number, FoundIndex, Index;
   char Response;

   First = 0;
   Last = Size-1;
   cout << "The array is: ";
   for (Index = First; Index <= Last; ++Index)
      cout << A[Index] << " ";
   cout << "\n";

   do
   {  cout << "Enter a number to find: ";
      cin >> Number;
      FoundIndex = BinSearch(A, First, Last, Number);
      if (FoundIndex == -1)
	 cout << "\nArray searched and " << Number << " not found!\n";
      else cout << "The target " << Number << " was found at index " <<
		       FoundIndex << "\n";

      cout << "\nContinue? ";
      cin >> Response;
   }  while ((Response != 'n') && (Response != 'N'));

   return (0);
}