// File:  BnSearch.cpp
// SEARCHES A SORTED ARRAY OF INTEGERS FOR A GIVEN ELEMENT USING
// A BINARY SEARCH ALGORITHM

int bin_search
     (const apvector <int>& items(),		//IN: the array being searched
      int target)					//IN:  the target being sought

// Performs a binary search of an ordered array
// Pre:  The elements of items() are in increasing order.
// Post: Returns the subscript of the target if found; otherwise.
//          returns -1.
{
   // Local variables
   int first;			// subscript of first element in array
   int middle;		// subscript of middle element in array
   int last;			// subscript of last element in array

   // set first and last
   first = 0;
   last = items.length() - 1;

   while (first <= last)
   {
      // Invariant:  Target was not found and array bounds are proper
      middle = (first + last) / 2;
      if (target == items[middle])
         return (middle);
      else if (target < items[middle])
         last = middle -1;
      else // target > items[middle]
         first = middle + 1;
   }// end while

   // target was not found
   return -1;
} // end bin_search