/**------------------------- BiSearch.java ---------------------------
 Implements the binary search algorithm and a test driver.
 Also measures the performance of the algorithm in terms of iterations.
 @author Glenn D. Blank and Edwin J. Kay
---------------------------------------------------------------------*/

import ucomp.Input;

class BiSearch
{
   static final int NOTFOUND = -1; //return if search can't find key
   static int countSteps=0;  //Measure performance of BinarySearch

  /** Find key in sorted array between subscripts 0 and numEntries-1
   *  Returns either index of found item OR -1 indicating not found
   *  Precondition: The entries in sorted[] are in ascending order
  */
  static int BinarySearch(int key,int sorted[],int numEntries)
  { int first=0, //first index starts at 0 but may move with search
        last=numEntries-1;  //last may also move with search
    while (first <= last)
    { countSteps++;                    //count each iteration as a step
      int middle = (first + last) / 2; //find middle
      if (sorted[middle] == key)       //match?
         return middle;                //return index #
      else if (sorted[middle] < key)   //key above middle?
         first = middle + 1;           //move first past middle
      else last = middle - 1;          //move last below middle
    }
    return NOTFOUND;                   //key is not in sorted array
  } //BinarySearch

  /** Initialize an array of String and test BiSearch */
  static public void main(String args[])
  { final int MAXARRAY=1000;
    int ia[] = new int[1000];
    
    //Initialize array to contain odd numbers
    for (int i=0; i<MAXARRAY; i++)
       ia[i]=i*2+1;
    
    //Let user supply numbers to test BiSearch
    int userInput=701; //Start by demonstrating one example
    while(userInput != -1)
    { //Test BinarySearch method
      int index = BinarySearch(userInput,ia,MAXARRAY);
      if (index == NOTFOUND)
	    System.out.println(userInput + " not found in " +countSteps+" steps");
      else
  	    System.out.println("Found "+userInput+" at index " + index + 
  	                        " in " +countSteps+" steps");  	  
      //prompt for another value
      System.out.print("Enter another integer or -1 to exit: ");
      userInput=Input.getInt();
      countSteps = 0;    //Reset counter for next search
    }//while
  }//main
}//class BiSearch