Vorlesung Informatik 2 - Teil B: Theorie
1.4 Rekursive binäre Suche
Die binäre Suche lässt sich gut als Rekursion implementieren.
Da die Tiefe der Rekursion logarithmisch wächst, kann es auch zu keinem Problem mit der Tiefe des Stack kommen.
Der Algorithmus lässt sich so skizzieren:
melde("Denk Die eine Zahl zwischen 1 und 100");
sucheBinaer(1,100);'
...
void sucheBinaer(int min, int max){
if(min==max) {
melde("Die gesuchte Zahl ist "+min);
return;
}
int mitte=(min+max)/2;
if(frage("Ist die Zahl großer als " +mitte)) sucheBinaer(mitte+1, max);
else sucheBinaer(min,mitte);
}
Vergleichen Sie die beiden Lösungen mit Rekursion und Schleife miteinander.