Bei den neuen Regeln gewinnst du fast immer, wenn du eine Strategie
verwendest, bei der du den in Frage kommenden Bereich jedes Mal halbierst.
Ein Beispiel:
Algorithmisch kann man dies so formulieren:
binäre Suche
Mitte?
Wenn der Bereich eine gerade Zahl von Kästchen enthält, gibt es kein 'mittleres'. Man wählt dann eines der beiden, die der Mitte am nächsten sind.
so schnell!
Mit Hilfe der Halbierungsstrategie kommt man in 93,75% der Fälle mit vier oder weniger Klicks zum Ziel. Für die anderen 6,25% braucht man fünf Klicks.
Wie kommt man darauf?
Weil man in jedem Schritt weiß, ob man links oder rechts weitersuchen muss, spricht man von binärer Suche.
Du hast diese Strategie vorher nicht verwendet?
Dann probiere sie hier aus.
Anwendung
Viele Aufgaben in der Datenverarbeitung kann man als Suche nach einem Datensatz mit einem bestimmten Schlüssel charakterisieren. In unserem Beispiel sind die Kästchen die Datensätze und die Zahlen die Schlüssel.
Die Abspeicherung von Datensätzen als Feld mit aufsteigenden Schlüsseln ist für das Suchen also besonders günstig.
Einfügen ist umständlich!
Aber: Will man einen neuen Datensatz einfügen, so wird es sehr aufwendig, die Anordnung zu erhalten. Im Schnitt muss man dann nämlich die Hälfte aller Datensätze um eine Position nach rechts verschieben.
Um eine Zahl einzufügen müssen erst alle Felder mit größeren Zahlen verschoben werden:
Ein ähnliches Problem taucht auf, wenn man einen Datensatz löscht.
|
|
|
|
|
