Binäre Suche

[Horst]

hi,

es gibt eine Liste die durchsucht werden soll nach Zahl x zum Beispiel. Bei einer binären Suche wird die Liste im ersten Schritt geteilt und eine der beiden Hälften durchlaufen, um zu prüfen, ob sich x darin befindet. Je nach Ergebnis geht es im nächsten Schritt in der jeweiligen Hälfte weiter, wieder teilen usw. So ist x sehr schnell gefunden.

Dieser Algorithmus ist nicht neu, aber wie immer mache ich mir da so meine Gedanken darüber und komme zu folgendem Ergebnis:

Ich fasse die Liste von links UND von rechts an um nach x zu suchen. Das müsste doch von der Performanze noch ein bischen schneller sein oder wie seht ihr das? Letztendlich ist das doch auch eine quasi-binäre Suche oder?

Bitte mal Input.

Viele Grüße,
Horst Haselhuhn

[Tom]

Hello,

Bitte mal Input.

Eine binäre Suche kann man nur in sortierten Listen durchführen.
In anderen hat sie keinen Sinn.

Und da gibt es dann nur eine einzige richtige Vorgehensweise, wenn Dir kein Wert aus Versehen durchrutschen soll.

Ein harzliches Glückauf

Tom vom Berg

[Cheatah]

Hi,

Ich fasse die Liste von links UND von rechts an um nach x zu suchen. Das müsste doch von der Performanze noch ein bischen schneller sein oder wie seht ihr das?

wenn Du zwei parallele Prozesse zur Verfügung hast, die gemeinsam die selbe Performance benötigen wie eine einzelne Prüfung: Ja. Andernfalls eher nicht.

Letztendlich ist das doch auch eine quasi-binäre Suche oder?

Eher eine trinäre. Du musst mit Dritteln arbeiten.

Cheatah

[Horst]

hi,

Ich fasse die Liste von links UND von rechts an um nach x zu suchen. Das müsste doch von der Performanze noch ein bischen schneller sein oder wie seht ihr das?

wenn Du zwei parallele Prozesse zur Verfügung hast, die gemeinsam die selbe Performance benötigen wie eine einzelne Prüfung: Ja. Andernfalls eher nicht.

cool. Genau dieselbe Idee kam mir vorhin beim Grillen der 1. Mai-Bratwürste, danke Cheatah.

Aber auch den Anderen danke ich!!! Als Gegenleistung nochn Hack von mir bezüglich des Einfügens eines neuen Listenelements:

Wenn die Liste ohnehin nicht sortiert ist, warum sollte ich zum Einfügen eines neuen Listenelements die ganze Liste durchlaufen, um das Letzte Element zu finden; zum Anhängen? [so lehren es die alten Meister] Nicht mit mir *G.

Jedes neue Listenelement füge ich vor dem jeweiligen 1. Element der Liste ein, das ist viel einfacher, als erst die ganze Liste zu durchlaufen...

--Hotte

[Cheatah]

Hi,

wenn Du zwei parallele Prozesse zur Verfügung hast, die gemeinsam die selbe Performance benötigen wie eine einzelne Prüfung: Ja. Andernfalls eher nicht.
cool. Genau dieselbe Idee kam mir vorhin beim Grillen der 1. Mai-Bratwürste, danke Cheatah.

ist Dir auch eine Idee gekommen, wie Du dies in die Praxis umsetzt?

Jedes neue Listenelement füge ich vor dem jeweiligen 1. Element der Liste ein, das ist viel einfacher, als erst die ganze Liste zu durchlaufen...

Hm, normalerweise sind entsprechende Dinge bereits in vorliegenden Klassen oder anderen Sprachkonstrukten gekapselt. Mit was für Systemen arbeitest Du, dass Du sogar einfache Listen selbst baust?

Cheatah

[3vi1]

echo ($light == true) ? 'Guten Tag,' : 'Guten Abend,';

also die Binäre Suche ist eigentlich nur bei geordneten Reichen sinnvoll. Bsp.:

1,3,4,6,8,9,11,123,2222

Wenn ich nun die 123 suche, fange ich bei der 9 an und merke die 123 ist größer als 9. Also suche ich in weiter in den Zahlen rechts von der 9.  Alle Zahlen kleiner als 9 werden nicht durchsucht! Dadurch wird dieser Algorithmus so schnell. Allerdings wenn ich im rechten und linken Teil suchen würde, wäre der Vorteil dahin.

Grüße

Markus