/**
* Binary search is the fastest way to look for an element in a sorted array. 
* For the sake of definiteness, assume we are dealing with arrays of int. 
* @author Dung X. Nguyen - Copyright 1999 - All rights reserved.
* @since 12/05/99
*/
public class BinSearcher
{
	public final static BinSearcher Singleton = new BinSearcher ();

	private BinSearcher()
	{
	}

	/**
    * Finds a key in an array and returns the index where the key is found.
    * Here is the pseudo-code for binary search.
<Pre>
Let key be an int we want to find in an array A.
If key == the "middle" element of A, then return "middle" as the index where key is found.
If key < the "middle" element of A, then search for key in the array to the left of "middle".
If key > the "middle" element of A, then search for key in the array to the right of "middle".
If key is not found, return -1.
</Pre>
	 * @param A an array of int.
	 * @param lo index for the lower bound of the search range.
	 * @param hi index for the upper bound of the search range.
	 * @param key object of desire!
    * @return the index in A where key is found, -1 if key is not found. 
	 */
	public int getIndex(int[] A, int lo, int hi, int key)
	{
      if (hi < lo)
      {
         return -1;
      }
      int mid = (lo + hi + 1) / 2;
      if (key == A[mid])
      {
         return mid;
      }
      else if (key < A[mid])
      {
         return getIndex (A, lo, mid - 1, key);
      }
      else
      {
         return getIndex (A, mid + 1, hi, key);
      }
	}

	/**
    * Tests getIndex(...).
	 * @param args not used. 
	 */
	public static void main(String[] args)
	{
      int[] A0 = {};
      int[] A1 = {-7};
      int[] A2 = {-7, 9};
      int[] A3 = {-7, 9, 23};
      int key = -7;

      System.out.print("Index of " + key + " in A0 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A0, 0, A0.length-1, key));
       System.out.print("Index of " + key + " in A1 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A1, 0, A1.length-1, key));
      System.out.print("Index of " + key + " in A2 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A2, 0, A2.length-1, key));
      System.out.print("Index of " + key + " in A3 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A3, 0, A3.length-1, key));

      key = 9;
      System.out.print("Index of " + key + " in A1 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A1, 0, A1.length-1, key));
      System.out.print("Index of " + key + " in A2 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A2, 0, A2.length-1, key));
      System.out.print("Index of " + key + " in A3 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A3, 0, A3.length-1, key));

      key = 23;
      System.out.print("Index of " + key + " in A1 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A1, 0, A1.length-1, key));
      System.out.print("Index of " + key + " in A2 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A2, 0, A2.length-1, key));
      System.out.print("Index of " + key + " in A3 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A3, 0, A3.length-1, key));

      key = -8;
      System.out.print("Index of " + key + " in A1 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A1, 0, A1.length-1, key));
      System.out.print("Index of " + key + " in A2 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A2, 0, A2.length-1, key));
      System.out.print("Index of " + key + " in A3 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A3, 0, A3.length-1, key));

      key = 0;
      System.out.print("Index of " + key + " in A1 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A1, 0, A1.length-1, key));
      System.out.print("Index of " + key + " in A2 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A2, 0, A2.length-1, key));
      System.out.print("Index of " + key + " in A3 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A3, 0, A3.length-1, key));

      key = 13;
      System.out.print("Index of " + key + " in A1 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A1, 0, A1.length-1, key));
      System.out.print("Index of " + key + " in A2 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A2, 0, A2.length-1, key));
      System.out.print("Index of " + key + " in A3 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A3, 0, A3.length-1, key));
      
      key = 25;
      System.out.print("Index of " + key + " in A1 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A1, 0, A1.length-1, key));
      System.out.print("Index of " + key + " in A2 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A2, 0, A2.length-1, key));
      System.out.print("Index of " + key + " in A3 = ");
      System.out.println (BinSearcher.Singleton.getIndex (A3, 0, A3.length-1, key));
	}
}