import java.io.*;

public class BinarySearchMain
{
	public static void main (String[ ] args) 
      	{
          final String ARRAY_MESSAGE =
              "The array on which binary searches will be performed is:\n" +
              "Ada, Ben, Carol, Dave, Ed, Frank, Gerri, Helen, Iggy, Joan";

          final String SENTINEL = "***";

          final String PROMPT =
              "\n\nPlease enter a name to be searched for in the array.  The " +
              "sentinel is " + SENTINEL + ".\n";

          final String[ ] names = {"Ada", "Ben", "Carol", "Dave", "Ed", "Frank",
                                   	    "Gerri", "Helen", "Iggy", "Joan"};

          final String FOUND = "That name was found at index ";

          final String NOT_FOUND = "That name was not found, but could be " +
                                   		"inserted at index ";

          String name;

          BufferedReader keyboardReader = new BufferedReader
                					(new InputStreamReader (System.in));

          int index;

          System.out.println (ARRAY_MESSAGE);
          while (true)
          {
	    	try
	    	{
              		System.out.print (PROMPT);
              		name = keyboardReader.readLine ();
              		if (name.equals(SENTINEL))
                 		break;
              		index = binarySearch (names, 0, names.length - 1, name);
              		if (index >= 0)
                 		System.out.println (FOUND + index);
              		else
                 		System.out.print (NOT_FOUND + (-index - 1));
	   	} // try
	   	catch (IOException e)
	   	{
			System.out.println (e);
	   	} // catch
          } // while
	} // method main


	/**
 	 * Searches the specified array for the specified object using the binary
 	 * search algorithm.  The array must be sorted into ascending order
 	 * according to the <i>natural ordering</i> of its elements (as by
 	 * <tt>Sort(Object[ ]</tt>), above) prior to making this call.  If it is
 	 * not sorted, the results are undefined.  If the array contains multiple
 	 * elements equal to the specified object, there is no guarantee which
 	 * one will be found.  The worstTime(n) is O(log n).
 	 *
 	 * @param a the array to be searched.
 	 * @param first the smallest index in the region of the array now being searched.
 	 * @param last the largest index in the region of the array now being searched.    
 	 * @param key the value to be searched for.
 	 *
 	 * @return index of the search key, if it is contained in the array;
 	 *	       otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
 	 *	       <i>insertion point</i> is defined as the point at which the
 	 *	       key would be inserted into the array: the index of the first
 	 *	       element greater than the key, or <tt>a.length</tt>, if all
 	 *	       elements in the array are less than the specified key.  Note
 	 *	       that this guarantees that the return value will be &gt;= 0 if
 	 *	       and only if the key is found.
 	 *     
 	 * @throws ClassCastException if the array contains elements that are not
 	 *	       <i>mutually comparable</i> (for example, strings and integers),
 	 *         or the search key in not mutually comparable with the elements
 	 *         of the array.
 	 * @see Comparable
 	 * @see #sort(Object[ ])
 	 */ 
	public static  int binarySearch(Object[ ] a, int first, int last, Object key) 
	{
   	 	if (first <= last) 
      		{
            		int mid = (first + last) / 2;
            		Comparable midVal = ((Comparable)a [mid]);
            		int comp = midVal.compareTo (key);
            		if (comp < 0)
                 		return binarySearch (a, mid + 1, last, key);
            		if (comp > 0)
                 		return binarySearch (a, first, mid - 1, key);
            		return mid;  // key found
      		} // if first <= last
      		return -first - 1; // key not found; belongs at a[first]
	} // method binarySearch

} // BinarySearchMain