package coahranm.algorithms;

public class Search {
   //binary search

   /* Algorithm: binary search
    * 
    * @param a
    *    array of values to search in
    * @param key
    *    key to search for
    * @pre
    *    elements in array a are sorted
    * @returns
    *    if key is in array: position in array where key was found
    *    if key is not in array: -1
    */
   public static int binary_search(int[] a, int key) {
      int low = 0;
      int high = a.length - 1;
      while (low <= high) {
         int mid = (low + high)/2;
         if (a[mid] < key) {
            low = mid + 1;
         }
         else if (a[mid] > key) {
            high = mid - 1;
         }
         else {
            return mid;
         }
      }//while
      
      //if we get here, key was not found
      return -1;
   }//binary_search(int[], int)
   
}//class Search