Suche nach einem Algorithmus (Version der 2-dimensionalen Binärsuche)

Einfache Lösung: gehe zuerst in X-Richtung und dann in Y-Richtung.

Überprüfung (0,50); Wenn es 0 ist, überprüfen Sie (0,75); bis Sie nebeneinander 0 und 1 finden. Dann gehen Sie von dort in Y-Richtung.

Zweite Lösung:

Überprüfen Sie das Element (50,50). Wenn es 1 ist, überprüfe (25,25), bis Du 0 findest. Weiter, bis Du neben (X, X) und (X + 1, X + 1) 0 und 1 findest. Dann test (X, X +1) und (X + 1, X). Keiner oder einer von ihnen wird 1 sein. Wenn beides nicht der Fall ist, sind Sie fertig. Wenn nur eine, sagen wir zum Beispiel (X + 1, X), dann wissen Sie, dass die Größe der Box zwischen (X + 1, X) und (100, X) liegt. Verwenden Sie die binäre Suche, um die Höhe der Box zu finden.

BEARBEITEN : Wie Chris betont hat, scheint der einfache Ansatz schneller zu sein.

Zweite Lösung (modifiziert):

Überprüfen Sie das Element (50,50). Wenn es 1 ist, überprüfe (25,25), bis Du 0 findest. Weiter, bis Du neben (X, X) und (X + 1, X + 1) 0 und 1 findest. Dann test (X, X +1). Wenn es 1 ist, dann binäre Suche in Zeile (X, X + 1) ... (X, 100). Sonst binäre Suche in Zeile (X, X) ... (100, X).

Selbst dann prüfe ich hier wahrscheinlich ein totes Pferd. Wenn es schneller wird, dann um vernachlässigbaren Betrag. Dies ist nur für theoretischen Spaß. :)

EDIT 2 Wie Fezvez und Chris es ausdrückten, teilt die binäre Suche den Suchraum am effizientesten in zwei Teile ein; Mein Ansatz teilt den Bereich auf 1/4 und 3/4 Stücke. Fezvez wies darauf hin, dass dies durch eine vorherige Berechnung des Teilungsfaktors behoben werden könnte (dies wäre jedoch eine zusätzliche Berechnung). In der modifizierten Version meines Algorithmus wähle ich die Richtung, wohin ich gehen soll (X- oder Y-Richtung), was effektiv auch den Suchraum in zwei teilt und dann binäre Suche durchführt. Zusammenfassend zeigt dies, dass dieser Ansatz immer etwas langsamer sein wird. (und komplizierter zu implementieren.)

Danke, Igor Oks, für die interessante Frage. :)

Bearbeiten: Die optimale Lösung besteht aus zwei einfachen binären Suchen.

Es tut mir sehr leid für den langen und komplizierten Beitrag, den ich unten gemacht habe. Worin besteht das Problem im Wesentlichen darin, einen Punkt in einem Raum zu finden, der 100 * 100 Elemente enthält. Das Beste, was Sie tun können, ist, bei jedem Schritt diesen Raum in zwei Teile zu teilen. Sie können es auf eine verschlungene Art und Weise tun (die, die ich im Rest des Posts gemacht habe). Aber wenn Sie erkennen, dass eine binäre Suche auf der X-Achse den Forschungsraum bei jedem Schritt noch in zwei teilt (dasselbe gilt für das Y Achse) dann verstehen Sie, dass es optimal ist.

Ich ließ immer noch die Sache, die ich getan habe, und es tut mir leid, dass ich einige bestätigende Aussagen darin gemacht habe.

Wenn Sie nach einem einfachen Algorithmus suchen (obwohl nicht optimal), führen Sie die binäre Suche zweimal wie vorgeschlagen aus.

Wenn Sie jedoch einen optimalen Algorithmus wünschen, können Sie gleichzeitig nach der Grenze für X und Y suchen. (Sie müssen beachten, dass die beiden Algorithmen dieselbe asymptotische Komplexität haben, aber der optimale Algorithmus wird immer noch schneller sein)

In allen folgenden Grafiken befindet sich der Punkt (0, 0) in der unteren linken Ecke.

Wenn Sie einen Punkt auswählen und das Ergebnis erhalten, schneiden Sie Ihren Platz in zwei Teile . Wenn Sie darüber nachdenken, ist das tatsächlich die größte Menge an Informationen, die Sie daraus ziehen können.

Wenn Sie den Punkt (das schwarze Kreuz) auswählen und das Ergebnis 1 ist (rote Linien), bedeutet dies, dass der gesuchte Punkt nicht im grauen Bereich sein darf (also muss in dem verbleibenden weißen Bereich sein)

Andererseits, wenn der Wert 0 ist (blaue Linien), bedeutet dies, dass der Punkt, nach dem Sie suchen, nicht im grauen Bereich sein darf (muss also in dem verbleibenden Weiß sein) Bereich)

Wenn Sie also ein Ergebnis von 0 und ein Ergebnis von 1 erhalten, erhalten Sie Folgendes:

Der Punkt, nach dem Sie suchen, ist entweder in Rechteck 1, 2 oder 3. Sie müssen nur die zwei Ecken von Rechteck 3 überprüfen, um zu wissen, welches der drei Rechtecke das gute ist.

Also ist der Algorithmus der folgende:

• Beachten Sie, wo sich die linke untere Ecke und die rechte obere Ecke des Rechtecks ​​befinden, mit dem Sie arbeiten.

• Machen Sie eine binäre Suche entlang der Diagonale des Rechtecks ​​, bis Sie mindestens einmal auf ein Ergebnis 1 und einmal auf ein Ergebnis 0 gestoßen sind.

• Überprüfen Sie die 2 anderen Ecken des Rechtecks ​​3 (Sie werden die Werte der beiden Ecken auf der Diagonale bereits kennen). Es ist möglich, nur eine Ecke zu überprüfen, um das rechte Rechteck zu erkennen (aber Sie werden müssen die zwei Ecken überprüfen, wenn das rechte Rechteck das Rechteck ist 3)

• Bestimmen Sie, ob der gesuchte Punkt in Rechteck 1, 2 oder 3 liegt

• Wiederholen Sie dies, indem Sie das Problem auf das gute Rechteck reduzieren, bis das letzte Rechteck auf einen Punkt reduziert ist: Es ist der Wert, nach dem Sie suchen

Edit: Wenn Sie die Supremum-Optimalität haben möchten, würden Sie nicht, wenn Sie den Punkt (50, 50) wählen, den Raum nicht zu gleichen Teilen schneiden. Eins ist dreimal größer als das andere. Idealerweise wählen Sie einen Punkt, der den Raum in zwei gleiche Bereiche (bereichsweise) schneidet.

Sie sollten einmal am Anfang den Wert von factor = (1.0 - 1.0/sqrt(2.0)) berechnen. Wenn Sie dann zwischen den Werten a und b schneiden möchten, wählen Sie den Schnittpunkt als a + factor*(b-a) . Wenn Sie das ursprüngliche 100x100 Rechteck an dem Punkt (100 * Faktor, 100 * Faktor) schneiden, haben die zwei Regionen eine Fläche (100 * 100) / 2, wodurch die Konvergenz schneller wird.

Führen Sie Ihre binäre Suche zweimal aus. Bestimmen Sie zuerst X, indem Sie die binäre Suche in der letzten Zeile ausführen und dann Y, indem Sie die binäre Suche in der letzten Spalte ausführen.

Verwenden Sie die binäre Suche für beide Dimensionen und den 1D-Fall:

1. Beginnen Sie mit j = 50. Jetzt hat die 1-D-Anordnung, die durch Variieren von i erhalten wird, die gewünschte Form - so finde X aus 1D-Fall.
2. Wenn X = 100 (d. h. keine Einsen), dann mache j = 75 (Mitte des Bereichs in j-Dimension) und wiederhole.
3. Wenn X & lt; 100, dann hast du es gefunden. Alles, was übrig bleibt, ist, i = X zu fixieren und Y aus dem 1D-Fall zu finden.