Warum kann die binäre Suche in einem unsortierten Array nicht verwendet werden?

Stellen Sie sich vor, Sie suchen ein Haus in einer wirklich langen Straße mit 1000 Häusern. Dies ist die Zukunft und wir haben die Fähigkeit zum Teleportieren gemeistert. Alles, was Sie haben, ist die Adresse, aber Sie wissen nicht, welche Häuser Adressen haben. Sie könnten mit 1, 5, 9, 19, 25, 28, 37 usw. nummeriert sein. Städte lassen diese Lücken absichtlich, um Adressen zu haben, die sie verwenden können, wenn später neue Häuser gebaut werden.

Der einfachste Weg, das Haus schnell zu finden, wäre, sich zur Hälfte der Straße zu teleportieren. Sie können sich die Adresse des Hauses ansehen, in dem Sie sich befinden. Wenn das Haus, das Sie suchen, eine größere Nummer ist, wissen Sie, dass es eines der Häuser weiter die Straße hinunter sein muss. Aber wenn das Haus, das Sie suchen, eine kleinere Nummer ist, muss es in die andere Richtung gehen.

Durch Teleportieren bis zur Hälfte haben Sie die Anzahl der zu durchsuchenden Häuser halbiert. Das erste Mal hast du dich auf halbem Weg zum 500. Haus auf der Straße teleportiert. Sie können die Häuser jedoch wieder halbieren, indem Sie den Vorgang wiederholen. Ist die gewünschte Hausnummer größer, teleportiert man sich zum 750. Haus. Ist die gewünschte Hausnummer kleiner, teleportiert man sich zum 250. Haus. Sie überprüfen noch einmal und beginnen schnell einzugrenzen, wo das Haus sein muss.

Da jeder Teleport die Anzahl der Häuser halbiert, finden Sie garantiert das gewünschte Haus in 11 Teleporten oder weniger. Dies ist viel schneller, als alle 1000 Häuser nacheinander zu überprüfen. Genau so funktioniert eine binäre Suche. Der Computer geht zur Hälfte einer sortierten Liste und überprüft dann, ob das Gewünschte näher am Anfang oder am Ende liegt. Es wiederholt den Vorgang und halbiert jedes Mal, wie viel gesucht werden muss.

Dies setzt voraus, dass die Liste sortiert ist. Kommen wir zurück zur Hausanalogie. Nehmen wir an, alle Häuser auf der Straße wären zufällig nummeriert (54, 1009, 2, 4006, 57, 186, 17, ...), dann würde es nicht helfen, zur Hälfte zu gehen. Wenn Sie zum 500. Haus gehen, können Sie nicht wissen, ob das gewünschte Haus rechts oder links liegt, da sie nicht in Ordnung sind. Die einzige Möglichkeit, das richtige Haus zu finden, besteht darin, sie einzeln zu überprüfen.

Binäre Suchen werden von Menschen die ganze Zeit in gewissem Umfang verwendet. Wenn wir in einem Telefonbuch nach Personen suchen, verwenden wir einen ähnlichen Prozess, indem wir nahe an der Stelle blättern, an der wir denken, dass es sein könnte, und dann ein paar Seiten vor- oder zurückblättern, bis wir die richtige Telefonnummer gefunden haben. Wären die Namen im Telefonbuch nicht geordnet oder nur zufällig eingetragen, wäre es praktisch unmöglich, das Gesuchte zu finden.