public class BinSearch1
{
   public static class MyEntry
   {
      int key;
      String  value;

      public MyEntry( Integer k, String v )
      {
	  key = k;
	  value = v;
      }


      public String toString()
      {
          return ( "(" + key + "," + value + ") " );
      }
   }

   public static int BinSearch(MyEntry[] A, int N, int k)
   {
      int low, high, mid;

      low = 0;             // low end
      high = N-1;          // high end
      mid = (high + low)/2;
   
      while ( low <= high )
      {
   	 mid = (high + low)/2;      // Middle element
/*
         System.out.println(">>> low = " + low + ", high = " + high 
				+ ", mid = " + mid + " (key = " + k + ")" );
*/ 
   	 if ( A[mid].key == k )
	 {
	    return( mid );    // found
	 }

	 if ( k < A[mid].key )
	 {
	    high = mid - 1;    // Search lower half
         }
	 else
	 {
	    low = mid + 1;    // Search upper half              
         }
      }

/*
      Always: high < low 
      System.out.println("*****  low = " + low + ", high = " + high );
      System.out.println("A[low] = " + A[low] + ", A[high] = " + A[high]
				+ " (key = " + k + ")" );
*/
      if ( high >= 0 && k <= A[high].key )
         return high;

      if ( low < N && k <= A[low].key )
         return low;

      return N;   // Exceeded !
   }

   public static void main( String[] args )
   {
      MyEntry[] OM = new MyEntry[8];

      OM[0] = new MyEntry( 4, "a" );
      OM[1] = new MyEntry( 7, "b" );
      OM[2] = new MyEntry( 9, "c" );
      OM[3] = new MyEntry( 14, "d" );
      OM[4] = new MyEntry( 18, "e" );
      OM[5] = new MyEntry( 23, "f" );
      OM[6] = new MyEntry( 29, "g" );

      for ( int i = 0; i < OM.length; i++ )
         System.out.print( i + ":" + OM[i] );
      System.out.println();
      System.out.println();

      int N = 7;

      System.out.println("BinSearch(2) = " + BinSearch(OM, N, 2) );
      System.out.println("BinSearch(4) = " + BinSearch(OM, N, 4) );
      System.out.println("BinSearch(5) = " + BinSearch(OM, N, 5) );
      System.out.println("BinSearch(7) = " + BinSearch(OM, N, 7) );
      System.out.println("BinSearch(8) = " + BinSearch(OM, N, 8) );
      System.out.println("BinSearch(9) = " + BinSearch(OM, N, 9) );
      System.out.println("BinSearch(13) = " + BinSearch(OM, N, 13) );
      System.out.println("BinSearch(14) = " + BinSearch(OM, N, 14) );
      System.out.println("BinSearch(16) = " + BinSearch(OM, N, 16) );
      System.out.println("BinSearch(18) = " + BinSearch(OM, N, 18) );
      System.out.println("BinSearch(20) = " + BinSearch(OM, N, 20) );
      System.out.println("BinSearch(23) = " + BinSearch(OM, N, 23) );
      System.out.println("BinSearch(26) = " + BinSearch(OM, N, 26) );
      System.out.println("BinSearch(29) = " + BinSearch(OM, N, 29) );
      System.out.println("BinSearch(33) = " + BinSearch(OM, N, 33) );
      System.out.println("BinSearch(39) = " + BinSearch(OM, N, 39) );
      System.out.println("BinSearch(93) = " + BinSearch(OM, N, 93) );

   }
}