lassen Sie uns sagen, dass wir eine geordnete Array-Elemente wie diese enthält,binäre Suche in Array, das Angebot enthält
[1, 2-5, 6, 8-9, 11-13], 2-5 ist ein Bereich, der 2, 3, 4 und 5 darstellt, wenn wir "4" finden wollen, dann ist Index 1 (von 0 beginnend) die Antwort, die wir brauchen.
Es ist möglich, dass wir binäre Suche wie diese Art von Elementen mit Konstantenraum und Log (n) Zeit anwenden?
Sie können einfach verwenden binäre Suche, das Konzept wird auch mit den Bereichen wie ein Charme arbeiten. Tatsächlich ist dies ein Konzept, das üblicherweise verwendet wird, um die Komplexität von Zeit und Raum zu reduzieren, zum Beispiel in gap encoding. Sie müssen es jedoch selbst schreiben, anstatt eine Bibliothek zu verwenden, da die Bibliotheks-Methode die Bereiche wahrscheinlich nicht akzeptiert.
Lassen Sie uns Index gehen durch die Ausführung einer binären Suche auf Ihrer gegebenen Eingabe von [1, 2-5, 6, 8-9, 11-13] für den Wert der Suche die ist kurz.
Das Array [1, 2-5, 6, 8-9, 11-13] hat Länge , die wir für den Index in der Mitte entscheiden, welche ist. Es liest dort den Wert 6 ein. Wir suchen nach dem Wert 4, also setzen wir die Suche nach links fort.
Wir reduziert nun das Suchintervall auf [1, 2-5, 6], Länge und wir für den mittleren Index entscheiden. Es liest 2-5. Als 4 ist in diesem Bereich haben wir fertig und geben Index als Ergebnis zurück.
Wenn zum Beispiel es 5-7 es lesen würde, dann würden wir die Suche nach links weiter als nicht innerhalb 5-7 ist. Analog würden wir die Suche nach rechts fortsetzen, wenn sie 1-3 lesen würde. Hier
ist eine Erklärung für binäre Suche mit einigen Pseudo-Code: Binary search algorithm at Wikipedia
Wenn Sie Probleme haben, die Umsetzung als nur Ihre Frage bearbeiten und zeigen Sie uns, was Sie bisher getan haben, werden wir dann anpassen und Hilfe.
danke, ich habe Probleme mit der Bereichs-Elementsuche bekommen, ich verstehe es jetzt, wenden Sie einfach die normale binäre Suche an, aber ändern Sie die Vergleichsmethode (Suchnummer und Bereichs-Element) wie "<" und "==". – Hao
Nach der binären Suche müssen Sie die Endelemente wie 2 und 5 vergleichen und daraus schließen, wo im ersten Teil oder im zweiten Teil gesucht werden soll. – bigbounty
Ja. Sie müssen nur benutzerdefinierten Vergleichscode verwenden, aber es wird immer noch die gleiche Komplexität haben. – BladeCoder
Warum sollten Sie es zuerst ausprobieren und dann Ihren Code posten, wenn Sie auf ein Problem stoßen? – trincot