class NichtGefunden extends Exception{
	private static final long serialVersionUID = 7526471155622776147L;
  private String message;
  public NichtGefunden(String meldung){ message = meldung; }
  public String getMessage(){ return message;}
} // Ende der Klasse NixDaException

class Element implements Comparable{
    int inhalt;
    Element(int i){ inhalt = i;}
    public int compareTo(Object o){
    Element e2 = (Element) o;
    int inhalt2 = e2.inhalt;
    if (inhalt == inhalt2) return 0;
    if (inhalt <  inhalt2) return -1;
    return 1;
  }
}

class MyRandom{
    static private int max = 52;
    static private java.util.Random RGen = new java.util.Random();
    static void setMax( int m){ max = m;}
	static Element zufall(){
	    int i = Math.abs(RGen.nextInt());
	    return new Element(i % max);
	    }
}  


class BinaerSuche {
    final int anzahl  = 42;
    Element[] cont    = new Element[anzahl];
    
    BinaerSuche(){
      for (int i=0; i < cont.length; i++) cont[i] = MyRandom.zufall();
    }
    
	int rekBinSuche(Element[] a, Element x, int min, int max) throws NichtGefunden{
		if (min > max) throw new NichtGefunden("Nix da");		
		int m = (min + max)/2;
		Element am = a[m];
		int comp = x.compareTo(am);
		if (comp == 0) return m;
		if (comp  < 0) return rekBinSuche(a, x, min, m-1);
		return rekBinSuche(a, x, m+1, max);
	}
	
	int binSuche(int x) throws NichtGefunden {
		return rekBinSuche(cont, new Element(x), 0, cont.length-1);
	}

}

public class BinSuche {

    public static void main(String args[]) {
        final int such  = 42;
        System.out.println("Binäre Suche ");
        System.out.println("Suche: "+such);
        for (int k = 0; k < 10; k++){
            BinaerSuche b = new BinaerSuche();
            try {
            int index = b.binSuche(such);
            System.out.println("Gefunden bei Index: "+index);
            }
            catch(NichtGefunden e){
		    System.out.println(such + " wurde nicht gefunden!");
		    }
		  }
 }       
}