BinarySearcher.java Page 1


    1	/**
    2	   A class for executing binary searches through an array.
    3	*/
    4	public class BinarySearcher
    5	{
    6	   /**
    7	      Constructs a BinarySearcher.
    8	      @param anArray a sorted array of integers
    9	   */
   10	   public BinarySearcher(int[] anArray)
   11	   {
   12	      a = anArray;
   13	   }
   14	
   15	   /**
   16	      Finds a value in a sorted array, using the binary
   17	      search algorithm.
   18	      @param v the value to search
   19	      @return the index at which the value occurs, or -1
   20	      if it does not occur in the array
   21	   */
   22	   public int search(int v)
   23	   {
   24	      int low = 0;
   25	      int high = a.length - 1;
   26	      while (low <= high)
   27	      {
   28	         int mid = (low + high) / 2;
   29	         int diff = a[mid] - v;
   30	
   31	         if (diff == 0) // a[mid] == v
   32	            return mid;
   33	         else if (diff < 0) // a[mid] < v
   34	            low = mid + 1;
   35	         else
   36	            high = mid - 1;
   37	      }
   38	      return -1;
   39	   }
   40	
   41	   private int[] a;
   42	}
   43