Binäre Suchprobleme?

Question

Mögliches Duplikat:
Was sind die Fallstricke bei der Implementierung der binären Suche?

Ich habe mir die Wikipedia-Seite für Binäre Suche und stolperte über ein Zitat von Knuth:

"Obwohl die Grundidee der binären Suche vergleichsweise einfach ist, können die Details erstaunlich knifflig sein.

Ich erinnere mich, dass ich im Rahmen meines Informatik-Lehrplans mehrere Binärsuchen implementiert habe, aber ich kann mich nicht erinnern, dass es besonders schwierig war. In diesem Artikel heißt es jedoch, dass 90 % der befragten Fachleute auch nach mehreren Stunden nicht in der Lage sind, eine solche Suche zum Laufen zu bringen. Ich möchte annehmen, dass dies nicht daran liegt, dass es sich um schlechte Programmierer handelt, sondern dass es Randfälle gibt, die bei naiven Implementierungen nicht berücksichtigt werden.

Was sind die Details, auf die sich Knuth bezieht? Was sind die üblichen Probleme, die bei der Implementierung eines binären Suchalgorithmus zu beachten sind?

Anmerkung: Ich habe den Artikel von Bloch über die Programmier-Perlen Fehler (Überlauf eines int für den Mittelpunkt). Gibt es noch etwas anderes?

Answer 1

Da ich beruflich mit der Java-Welt zu tun habe, erinnere ich mich este . Ich war ziemlich überrascht, als ich es zum ersten Mal las, also könnte dies eines der Dinge sein, über die Donald gesprochen hat.

Answer 2

Eine der besten Referenzen für den kniffligen Punkt der binären Suche ist Jon Bentleys Programmierperlen.

Le site ganzes Kapitel 4 geht auf dieses Problem ein, das viele falsche Versionen der binären Suche zeigt.

Sie möchten z. B. die erste Zahl finden, die größer oder gleich Ihrer Abfrage ist x . Denken Sie an die +1 -1 die darin enthaltenen Probleme. Wie können Sie beweisen, dass Ihr Verfahren genau richtig ist?

Wenn Sie über diese Probleme nachdenken, werden Sie feststellen, dass es nicht so einfach ist.