import algds.IOUtils;
/**
 * Binaere Suche am Beispiel des Zahlenratens.
 * Erweitert fuer beliebige sortierte int-Felder.
 * 
 * @author Christian Semrau, 07.12.1999
 * <a href="mailto:Christian.Semrau@student.uni-magdeburg.de">
 * Christian.Semrau@student.uni-magdeburg.de</a>
 */
class ChS_Aufg28 {

/**
 * Ermittelt eine vom Benutzer gemerkte Zahl.
 * Funktioniert fuer jedes int-Feld, das die erlaubten Zahlen sortiert enthaelt.
 */
public static void main(java.lang.String[] args) {
  System.out.println("AlgDs WS99 Aufgabe 28, Christian Semrau 07.12.1999");

  // Anzahl der Fragen, Auswahl des Benutzers
  int fragen = 0, a;

  // Anzahl der Elemente
  int max = 100;
  // Feld anlegen
  int[]feld = new int[max];
  // Feld fuellen
  for(int i=0; i<max; i++)
	// sieh die mal an, was bei feld[i]=(i+1)*(i+1); passiert
	feld[i]=(i+1);

  // untere und obere Grenze, Mitte
  int un = 0, ob = max-1, mid;

  System.out.println("Merk dir eine Zahl von "+feld[un]+" bis "+feld[ob]+"!");

  // Label zum Verlassen der Schleife
  // fiel mir als erstes ein, es geht auch mit "boolean gefunden"
  schleife:
  do {
	// Mitte berechnen
	mid = (un+ob)/2;
	
	// Benutzer fragen
	System.out.println("Ist deine Zahl kleiner[1], gleich[2] oder groesser[3]"
	  +" als "+feld[mid]+" ["+feld[un]+"-"+feld[ob]+"]?");

	// Eingabe holen und Fragenzaehler erhoehen
	do{ a=IOUtils.readInt(); }while(a<1||a>3);
	fragen++;

	// Auswertung
	switch(a){
	  // 1 -> gesuchte ist kleiner
	  // obere Grenze ist unter alter Mitte
	  case 1: ob = mid-1; break;
	  // 2 -> gleich
	  // Mitte ist genau das gesuchte Element
	  case 2: un = ob = mid; break schleife;
	  // 3 -> gesuchte ist groesser
	  // untere Grenze ist ueber alter Mitte
	  case 3: un = mid+1; break;
	}
  }while(un<=ob);

  if (un==ob)
	// gefunden
	System.out.println("Nach "+fragen+" Fragen ermittelt: "+feld[mid]);
  else
	// nicht gefunden -> feld[un] ist zu gross, feld[ob] ist zu klein
	System.out.println("Nicht gefunden! "+feld[ob]+"<x<"+feld[un]+"!");
} // main()
} // ChS_Aufg28