Unsere Dozentin demonstriert uns gerade praktisch die binäre Suche:
Sie hat ein Telefonbuch von Dortmund mitgebracht, dort hat ein Student pseudo-zufällig den Namen “Smolarek” reusgesucht.
Unsere Dozentin hat zunächst festgestellt, dass der Teil mit den Telefonnummern im Telefonbuch von Seite 40 bis Seite 632 geht. Die Mitte davon ist auf Seite 296 (das zu berechnen hat übrigens einige Studis durchaus zum Nachdenken angeregt…). Dort steht ein Herr Kaiser. Wir stellten fest, dass der Zielname Smolarek “größer” ist als Kaiser, also durfte ein Student das Telefonbuch an dieser Seite in der Mitte durchreißen, wir haben den vorderen Teil weggeschmissen und nur mit dem hinteren Teil mitgemacht.
Also ging es weiter mit dem Bereich 297 bis 632. In der Mitte stand eine Frau Küster. Smolarek ist größer als Küstner, also wieder durchreißen und vorderen Teil wegwerfen.
Rest: 465 bis 632, Mitte: “Prode”; Smolarek ist diesmal kleiner => durchreißen, und diesmal den hinteren Teil wegwerfen.
Rest: 465 bis 568, Mitte: “Stepniak”; Smolarek ist kleiner, hinteren Teil weg.
Rest: 527 bis 568, Mitte: “Schröder”; Smolarek größer, vorderen Teil weg.
Rest: 527 bis 537, Mitte: “Sprack”; Smolareck kleiner, hinteren Teil weg.
Ab hier habe ich irgendwie den Faden verloren… aber das ist nicht nur mir passiert, auch unsere Dozentin hat soeben festgestellt, dass “ö kleiner als o” ist. Dann hat sie soeben (ja, das ist live-Blogging!) das Mikro fallengelassen und es damit fast kaputtgemacht.
Inzwischen schnipselt sie mit einer Schere an den letzten paar Personen herum.
Fazit der ganzen Aktion: Wir haben eine Person im etwa 300.000 Personen umfassenden Dortmunder Telefonbuch mit genau 20 Vergleichen gefunden (theoretisch hätten 19 Vergleiche gereicht, jedoch hat, wie schon erwähnt die Mittelpunkt-Berechnung teilweise kleinere Probleme dargestellt 😉 ). Der Zeitaufwand für diese gaze Aktion warzwar enorm, der Lerneffekt aber auch – jetzt sollte eigentlich jetzt jeder hier im Hörsaal etwas mit der binären Suche anfangen können.
Spruch von Jan, beim Anblich der Professorin inmitten des Stapels von auseinander geschnittenen / -rissenen Telefonbuchteilen:
Hoffentlich sucht sie privat nicht auf diese Weise die Leute – sonst hätte sie nämlich einen etwas hohen Telefonbuch-Verbrauch.
😀