Diskussion:Binäre Suche/Archiv/1

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:Binäre Suche/Archiv/1#Thema 1]]

oder als Weblink zur Verlinkung außerhalb der Wikipedia

https://de.wikipedia.org/wiki/Diskussion:Bin%C3%A4re_Suche/Archiv/1#Thema_1

C

Hi!

Kann es sein, dass die Kommentare im C-Code vertauscht sind (dort wo "im linken Abschnitt weitersuchen" steht, müsste doch eigentlich lauten "im rechten Abschnitt weitersuchen" und umgekehrt, oder sehe ich das falsch?)?--Am0123456789 09:30, 25. Feb. 2009 (CET)

Ist richtig, so wie's z.Zt dasteht. --arilou (Diskussion) 10:02, 9. Jul. 2013 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:02, 9. Jul. 2013 (CEST)

Weise ~ Schlüssel

Hallo,

Müsste es nicht heissen :

Voraussetzung ist, dass die Elemente der Liste in einer dem Suchbegriff entsprechenden Weise mit einer Ordnungsrelation geordnet sind.

Jein. Der von dir gebrachte Einwand dass die Elemente bezüglich einer Relation geordnet sein müssen ist erst einmal komplett richtig. Aber der Teil mit dem "dem Suchbegriff entsprechenden Weise" stört mich. Was soll das bedeuten? Der Suchbegiff muss sich nur mit den Elementen des Array (Listen gehen übrigens nicht, da hier kein Elementfreier Zugriff möglich ist, und man somit nicht direkt in die Mitte springen kann) über die Relation vergleichen lassen. Wollte es eben mal umändern, aber leider fällt mir keine vernüftige Beschreibung ein, ohne gleich mit Relationen etc um mich zu werfen. (Und wenigstens der Einleitungssatz sollte bei einem derart leichten Algorithmus verständlich bleiben)... Falls also irgendwer eine Idee hat wie man es einbauen kann, immer rein in den Artikel. Der aktuelle Einleitungssatz ist nämlich momentan mindestens unvollständig wenn nicht falsch. Regnaron 14:36, 29. Jul 2005 (CEST)

Das Wort, das ihr sucht, nennt sich "(Such-)Schlüssel". Die Menge muss gemäß desselben Schlüssels geordnet sein, wie dann gesucht wird. --arilou (Diskussion) 10:04, 9. Jul. 2013 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:04, 9. Jul. 2013 (CEST)

Beispiele

Wie wären ein paar Beispiele in C, C++, Java etc.? Ich stelle mir z.B. soetwas vor: in einem 26 Elemente langem eindimensionalen Array in dem das Alphabet (ohne Umlaute) geschrieben wird. Dann wird D mit der Binärer Suche gesucht und auf der Konsole ausgegeben. --PhilippW 16:05, 21. Jun 2004 (CEST) (werde das Beispiel zu Java beisteuern)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:08, 9. Jul. 2013 (CEST)

Unterabschnitt Suchschritte berechnung

Hi, nachdem ich heute Mittag mal den Abschnitt Suchschritte berechnung gelöscht hatte da er in meinen Augen nur ein HOWTO zur Benutzung eines Taschenrechners darstellt (eben wie man den zweierlogarithmus einer Zahl berechnet) und somit nichts in diesem Artikel verloren hat, wurde der entsprechende Teil inzwischen wiederhergestellt. Da der entsprechende oder die entsprechenden User (war beides mal ein IP Adresse) also scheinbar ein Interesse an dem Unterabschnitt haben wollte ich das ganze mal hier zur Diskussion stellen bevor ich einen Edit War vom Zaun breche. IMHO hat wie gesagt die berechnung eines Logarithmus einer natürlichen Zahl mit dem Hilfsmittel eines Taschenrechners nichts in einem Artikel über einen Suchalgorithmus verloren. Dafür ist der Artikel Logarithmus da, und IMHO nicht die 100 Artikel über irgendwelche Suchalgorithmen wo man ab und an mal eine Zahl ausrechnen muss Regnaron 18:44, 3. Nov 2005 (CET)

Full Ack.

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:09, 9. Jul. 2013 (CEST)

Java-Fehler

Der Java-Code ist fehlerhaft. Sieht man schnell, wenn mann ihn ausprobiert und die Zeile

        	System.out.println("Suchergebnis: "+ suche( 'D' , alphabet));

durch

        for(char c='A', i=0; i<=alphabet.length-1; c++, i++)
         	System.out.println("Suchergebnis: "+ suche( c , alphabet));

ersetzt.

Aktueller Code funktioniert einwandfrei. --arilou (Diskussion) 10:20, 9. Jul. 2013 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:20, 9. Jul. 2013 (CEST)

Abschnitt Pseudocode

Ja, der Algorithmus ist so definitiv falsch!

Mit der hier gezeigten Berechnung der Mitte gelangt man nur in die untere Hälfte des aktuellen Intervalls:

        	Variable: Mitte = (ErstesElement + LetztesElement) DIV 2

Bei einem 0-basierten Array müsste es folgendermassen aussehen:

        	Variable: Mitte = (ErstesElement + LetztesElement) DIV 2 + ErstesElement

--Katja D 23:23, 10. Mär 2006 (CET)

Achtung! Die obige von KatjaD geäusserte Korrektur halte ich für schlichtweg falsch! entweder: (anfang + ende) / 2 oder : anfang + ((ende-anfang) / 2) (beides äquivalent, bis auf Integer-overflow, s.u.) Desweiteren ist es nicht nötig die Variable für die Mitte zu übergeben (wie es derzeit bei der rek. java-impl. getan wird), da diese sowieso direkt neu berechnet wird-> schlechter Programmierstil, soeben geändert

Sorry, aber ist der Teil

         Wenn S > als A[Mitte] ist dann 
              links weitersuchen  (LetztesElement = Mitte - 1)
         Sonst  
              rechts weitersuchen (ErstesElement  = Mitte + 1)
         Ende Wenn

nicht auch falsch? Es müsste doch genau anders herum sein, oder? Wenn mein SearchString größer als das Element in der Mitte ist, suche ich doch nicht in dem Teil weiter, in dem die Elemente noch kleiner sind (links)?!

         Wenn S < als A[Mitte] ist dann 
              links weitersuchen  (LetztesElement = Mitte - 1)
         Sonst  
              rechts weitersuchen (ErstesElement  = Mitte + 1)
         Ende Wenn

wäre somit die korrekte Formulierung, oder? Somit müsste es aber auch in den anderen Sprachen geändert werden. Einzige Ausnahme wäre, wenn das Array absteigend sortiert wäre. 1. steht davon aber nirgends etwas, und 2. wird sogar im ersten Abschnitt des Artikels erwähnt: "Ist es kleiner als das gesuchte Element, muss das gesuchte Element in der hinteren Hälfte stecken, falls es sich dort überhaupt befindet. Ist es hingegen größer, muss nur in der vorderen Hälfte weitergesucht werden.". --P.Soell 11:24, 2. Jan. 2007 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:23, 9. Jul. 2013 (CEST)

Vorschlag zur Implementierung in Delphi / Pascal

Bin ja nicht so der Wikipedia-Mensch, aber wenn ich es mache: So oder ähnlich könnte es in Delphi/Pascal aussehen:

Feld ist vom Typ TFeld welches TInhalt enhält. z.B. Integers, Chars oder auch Strings.

procedure binarysearch (suche: TInhalt; var Feld: TFeld; von, bis: integer; var gefunden: boolean);
var mitte: integer;
begin
  mitte:=(von + bis) div 2;
  if von > bis then
    gefunden:=false
  else if suche < Feld[mitte] then
    binarysearch(suche,Feld,von,mitte-1,gefunden)
  else if suche > Feld[mitte] then
    binarysearch(suche,Feld,mitte+1,bis,gefunden)
  else
    gefunden:=true
end;

Müsste so stimmen. P.S.: Könnte man natürlich auch als Funktionschreiben, man müsste nicht mal viel ändern. Nur

procedure binarysearch (suche: TInhalt; var Feld: TFeld; von, bis: integer; var gefunden: boolean);

zu

function binarysearch (suche: TInhalt; var Feld: TFeld; von, bis: integer):boolean;

und an den stellen wo gefunden steht einfach binarysearch hinsetzen.

--gez. MJ

Es gibt mittlerweile in Pascal-Beispiel im Artikel, somit:

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:24, 9. Jul. 2013 (CEST)

Fehler in binären Suchen

Joshua Bloch (ein Java-Entwickler) weist auf einen Fehler bei der Implementierung von binären Suchen hin, wenn man es so macht, wie auch hier angegeben [1]. Der Fehler existiert schon seit Jahrzehnten unentdeckt. Das Problem ist die Bildung des Mittelwertes:

Variable: Mitte = (ErstesElement + LetztesElement) DIV 2

Dies ist OK, solange man Integertypen mit beliebiger Genauigkeit hat. Ist der Datentyp jedoch begrenzt, wie es normalerweise bei Programmiersprachen der Fall ist, kann es bei sehr großen zu durchsuchenden Listen zum Überlauf bei der Addition kommen. Also: ErstesElement + LetztesElement > MaxInt. Das Problem tritt natürlich erst bei wahnsinnig großen Listen auf, wenn Integer 32 Bit sind, 1 davon fürs Vorzeichen draufgeht dann *kann* der Fehler ab etwa 2^30 Elementen auftreten. Bloch schlägt als Lösung folgende Zeile vor:

Variable: Mitte = ErstesElement + ((LetztesElement - ErstesElement) DIV 2)

Beim Pseudocode würde das Problem gar nicht auftreten, da die Maximalgröße der Datentypen da nicht definiert ist. Dennoch ändere ich den Code auch dort, damit der Fehler bei Übertragung in eine reale Programmiersprache vermieden wird. -- Dishayloo 09:38, 17. Jun 2006 (CEST)

chars only; code style

Noch zwei kleine Anmerkungen: Da wir im Java Beispiel nur auf chars arbeiten, sollte auch der Return-Wert ein char sein. System.out.prinln() kommt bestens mit chars zurecht, somit ist die String konvertierung hier unnötig. Zudem sollten gewisse Standards eingehalten werden. Ob man Variablen am Anfang nur groß oder klein schreibt (ist zwar im Java Standard festgelegt), sollte wenigstens im Programm eindeutig sein. Ähnliches gillt für Kommentare: teilweise zum Verständnis wichtige Kommentare wegzulassen ist zumindest unkonventionell (int Mitte = 0;), Kommentare in der Form " //Wiederhole" einzufügen jedoch schlicht überflüssig. --LautGelacht

Quatsch. Der Index in ein Feld kann von anderem Typ sein (Integer, Long), als der Sortierschlüssel. Auch in einem char[] können mehr als 256 Elemente drinstecken. --arilou (Diskussion) 10:29, 9. Jul. 2013 (CEST)

einfacher

Ich habe das Java-Beispiel drastisch vereinfacht, und zwar aus folgenden Gründen.

1. Es ist nur ein Beispiel, wir brauchen hier keine vollständigen Listings ablauffähiger Programme. Der erklärende Fließtext ist weitaus wichtiger, denn eigentlich geht es um den Algorithmus, nicht darum, ein Programmierhandbuch für Java zu schreiben.
2. In einem solchen Programmierhandbuch dürfte man dann auch auf das oben von Dishayloo bemängelte Problem ansprechen. Hier habe ich es entfernt, um den Code leichter verständlich zu machen.

--jpp ?! 10:05, 9. Aug 2006 (CEST)

---

alles:

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:29, 9. Jul. 2013 (CEST)

Abschnitt Komplexität

Hi!

Sehr angetan binnich von der Verständlichkeit des Artikels. Zum Abschnitt Komplexität hätte ichn Vorschlag, die vorgenannte weiter zu verbessern, nämlich mittels eines Zahlenbeispiels. Weil "log2n Schritte" ist ziemlich abstrakt.

Also:

Komplexität

Um in einem Array mit n Einträgen ein Element zu finden bzw. festzustellen, dass dieses sich nicht im Array befindet, werden maximal log2n Schritte benötigt. (Zahlenbeispiel: Die Suche in einem Array mit 2^16 (= 65536) Elementen ist in maximal 16 Schritte abgehandelt.) Somit liegt die binäre Suche, in der Landau-Notation ausgedrückt, in der Komplexitätsklasse O(log n). Damit ist sie deutlich schneller als die lineare Suche, welche allerdings den Vorteil hat, auch in unsortierten Arrays zu funktionieren. Noch schneller als die binäre Suche ist die Interpolationssuche.

(so ungefähr. Besonders formatierungsmäßig binnich ein Wiki-Nuller)
Ah, Zum Abschnitt "Algorithmus" weißich noch was. Nämlich, daß die binäre Suche im Falle des Nichtfindens immerhin die Position ermittelt, an der das Element wäre, also die eventuelle Einfügeposition

Also:

Ich finde dass auch eine Herleitung der Komplexität den Artikel bereichern würde, kann dazu allerdings selber auch nichts beitragen... -88.65.56.17 18:34, 28. Sep. 2007 (CEST)

1. Wer nicht weis, was ein Logarithmus ist, soll in selbigem Artikel nachlesen.
2. Eine Herleitung für log2(n) ist trivial: Mit jedem Schritt halbiert sich die Menge - wie oft geht das? - log2(n) oder log2(n)+1 Mal, also aufrunden.

--arilou (Diskussion) 10:42, 9. Jul. 2013 (CEST)

Algorithmus

Zuerst wird das mittlere Element des Arrays überprüft. Es kann kleiner, größer oder gleich dem gesuchten Element sein. Ist es kleiner als das gesuchte Element, muss das gesuchte Element in der hinteren Hälfte stecken, falls es sich dort überhaupt befindet. Ist es hingegen größer, muss nur in der vorderen Hälfte weitergesucht werden. Die jeweils andere Hälfte muss nicht mehr betrachtet werden. Ist es gleich dem gesuchten Element, ist die Suche (vorzeitig) beendet.

Jede weiterhin zu untersuchende Hälfte wird wieder gleich behandelt: Das mittlere Element liefert wieder die Entscheidung darüber, wo bzw. ob weitergesucht werden muss.

Die Länge des Suchbereiches wird von Schritt zu Schritt halbiert. Spätestens wenn der Suchbereich auf 1 Element geschrumpft ist, ist die Suche beendet. Dieses eine Element ist entweder das gesuchte Element, oder das gesuchte Element kommt nicht vor.

Im Falle des Nicht-Auffindens endet die binäre Suche an der "Einfüge-Position", also an der Position, an der das Element eingefügt werden kann, ohne die Sortierung des Arrays zu zerstören.

Der Algorithmus zur binären Suche wird entweder als Iteration oder Rekursion implementiert.

Mittlerweile erwähnt.

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:42, 9. Jul. 2013 (CEST)

Python-Implementierung

Hi, meiner Meinung nach, sollte die iterative Pythonimplementierung aktualisiert werden. Einfache Pythonstandards wurden dort gebrochen... was sagt ihr dazu?

--Mateusz87 20:58, 8. Mai 2007 (CEST)

Sei mutig!. --jpp ?! 23:22, 8. Mai 2007 (CEST)

6 Jahre alt, somit:

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:42, 9. Jul. 2013 (CEST)

Ist das wirkich Divide&Conquer?

Im Artikel steht " Der Algorithmus basiert auf dem Schema Teile und Herrsche." Ich glaube nicht dass das stimmt. Zumindest erkenne ich im Algorithmus dieses Schema nicht. Wenn man die binäre Suche einem Schema zuerdnen will, würde vielleicht der Greedy-Algorithmus besser passen. Was meint ihr denn?

Beides.

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:42, 9. Jul. 2013 (CEST)

Pseudocode

Habe den Pseudocode in Delphi vresucht zu Implementieren. Am Anfang hat er nur das mittlere Element ausgegeben wenn ich danach gesucht hab. Dann hab ich die Bedingung der Solange-Schleife geändert und jetzt funktioniert es.

Vorher lautete die Bedingung: Solange (SucheErfolgreich = falsch) und (Anfang ≤ Ende) mache

Habe sie abgeändert in: Solange (SucheErfolgreich = wahr) und (Anfang ≤ Ende) mache

--Jim C. 08:40, 18. Juni 2008 (GMT+1)

Da muss irgendetwas in Deiner Implementierung schiefgelaufen sein. SucheErfolgreich wird auf wahr gesetzt um die Schleife mit einem Treffer abzubrechen. Wenn die Prüfung - so wie Du es geändert hast - auf SucheErfolgreich = wahr erfolgt, dann wird niemals in die Schleife eingetaucht, da SucheErfolgreich vor der Schleife auf falsch gesetzt wird. Solange übersetzt sich in den meistens Programmiersprachen auf eine while-Schleife, ich erinnere mich nicht mehr daran ob es die in Pascal gab. Aber es gab in Pascal eine Repeat-Until-Schleife. Bei der wird abgebrochen wenn die Bedingung erfüllt ist, bei while (solange) wird abgebrochen, wenn die Bedingung NICHT erfüllt ist. -- Dishayloo + 00:32, 21. Jun. 2008 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:42, 9. Jul. 2013 (CEST)

Abschnitt Java

Ich möchte anfragen, ob die Java-Implementierung der binären Suche nicht eventuell fehlerhaft ist, da sich in der while-Schleifen-Bedingung die Variable "ergebnis" befindet, die zuvor nicht deklariert wurde. Der Code ist so, wie er auf der Seite steht, nicht kompilierbar und sollte daher vielleicht geändert/erweitert werden, sofern ich mit meiner Anmerkung richtig liege.

LG (nicht signierter Beitrag von 92.78.131.18 (Diskussion) 23:38, 15. Mai 2011 (CEST))

wohl erledigt:

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:42, 9. Jul. 2013 (CEST)

Fallstrick

Das grundsätzliche Problem wurde hier vor Jahren schonmal disuktiert (#Fehler in binären Suchen), ist aber in der derzeitigen Form erst seit einem Dreivierteljahr im Artikel. Ich glaube nicht, dass in einer (Wikipedia-naturgemäß) eher oberflächlichen Beschreibung des Algorithmus eine reine Implementierungsproblematik wie im Abschnitt Fallstrick so tiefgehend erläutert werden sollte. Der Algorithmus selbst ist an der Stelle ja nicht problematisch: Betrachte das mittlere Element, viel einfacher geht es nicht. Wenn jemand, verkürzt gesagt, unter bestimmten (zudem eher seltenen/unwahrscheinlichen) Umständen zu "blöd" ist, das mittlere Element korrekt zu ermitteln, dann ist das kein Problem des Algorithmus, sondern des Programmierers. --YMS 00:21, 8. Jan. 2012 (CET)

Abschnitt gibt's nicht mehr, somit:

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:42, 9. Jul. 2013 (CEST)

Erstes Bild falsch?

HI, bei der binären Suche muss jeweils der Abschnitt welcher durchsucht wird halbiert werden. Folglich muss die suche bei J beginnen da hier 4 elemente rechts als auch links davon liegen und nicht bei L!

Ich glaube, du hast übersehen, dass die tabelle rechts abgeschnitten ist, dort also noch viel kommen kann. --Nomen4Omen (Diskussion) 09:09, 26. Okt. 2012 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:42, 9. Jul. 2013 (CEST)

Implementierungen schwach

Alle Implementierungen sind schwach, weil: Wenn das Element nicht gefunden wurde, kann man

-Mitte

zurückgeben; das ist

• negativ, als "nicht-gefunden-Flag"
• und bietet die Information, wo das Element in etwa einsortiert gehören würde.

Derzeitige Beispiel-Implementierungen geben immer nur 0 oder -1 zurück.

Allerdings muss man aufpassen, was daraus wird, wenn das Element als erstes (-0 = +0) oder letztes einzufügen wäre, und vielleicht noch andere Fallstricke. Deswegen erst mal ein entsprechender Baustein. --arilou (Diskussion) 11:54, 8. Jul. 2013 (CEST)

Das gehört aber nicht mehr wirklich zum Konzept der binären Suche, den Rückgabewert auf Benutzbarkeit zu optimieren. Wikipedia ist kein Programmier-Lehrbuch, sondern gehört hier her: https://en.wikibooks.org/wiki/Algorithm_Implementation/Search/Binary_search --138.246.2.177 14:34, 8. Jul. 2013 (CEST)

"Das gehört aber nicht mehr wirklich zum Konzept der binären Suche" - WP:POV. Meiner Meinung nach gehört zu jeder Suche, beim Nicht-Finden eine möglichst gute Aussage zu liefern, wo das gesuchte hätte sein müssen.

Und afaik gibt es keine reale Implementierung der Binären Suche, die diese Chance nicht nutzt - mit Ausnahme hießiger Beispiel-Implementierungen... und sollten Beispiele nicht möglichst dem entsprechen, was es "da draußen" gibt?

Bzgl. "Programmier-Handbuch": Die Liste der Beispiele könnte ruhig reduziert werden auf

• das Pseudocode-Beispiel (Iterative Variante),
• ein Beispiel in einer "normalen" Sprache (Java,C,Pascal, aber nur eines, nicht alle!) (Rekursive Variante)
• und als Exot das Haskel-Beispiel.

--arilou (Diskussion) 09:30, 9. Jul. 2013 (CEST)

M.E. sollten aus didaktischen Gründen die Beispiele möglichst einfach gehalten werden. Das soll nicht gleichzeitig kurz heißen, ist es aber dann doch meistens. In den aufgeführten Beispielen sollte mMn. auch darauf verzichtet werden, beim Nicht-Finden eine Aussage zu liefern, wo das Gesuchte hätte stehen müssen, denn dafür müsste (soweit ich das gerade sehe) überall noch ein paar zusätzliche Zeilen Code sowie mindestens ein zusätzlicher Parameter eingeführt werden. Bin mir auch nicht sicher, ob das wirklich bei der Erklärung hilft und ich persönlich habe mich noch nie dafür interessiert, wenn das Element nicht gefunden wurde.

Für eine Reduktion der Anzahl der Beispiele bin ich auch. Mein Vorschlag wäre, das Beispiel aus C zu erhalten (klar :) ) (auch da es praktisch 1-zu-1 in C++ und Java übernommen werden kann) sowie Pascal (weil irgendwelche Leute noch immer was mit Dephi machen) und den Exoten Haskel. --Plankton314 (Diskussion) 11:36, 9. Jul. 2013 (CEST)

Hab' die C-Variante etwas überarbeitet (warum müssen in C Variablen auch heute noch nur aus 1 Buchstaben bestehen?!?).

Da das Pascal-Beispiel rekursiv ist, kann ich mit deiner Auswahl leben, von mir aus: OK.

--arilou (Diskussion) 14:56, 9. Jul. 2013 (CEST)

Ui, in der Pascal-Version war 'ne Endlos-Rekursion bei "nicht gefunden"! --arilou (Diskussion) 15:09, 9. Jul. 2013 (CEST)

Wo ich gerade drüber nachdenke, ist das Python-Beispiel wohl doch relevanter als das Pascal-Bsp. --Plankton314 (Diskussion) 15:08, 9. Jul. 2013 (CEST)

Dann aber davon die rekursive Variante. --arilou (Diskussion) 15:09, 9. Jul. 2013 (CEST)

Hab' jetzt entsprechend auskommentiert, was "überflüssig" ist. --arilou (Diskussion) 11:46, 17. Jan. 2014 (CET)

Und ich habe die zahlreichen auskommentierten Codeschnipsel entfernt, da die meisten didaktisch schlecht waren, zum Beispiel durch überflüssige Fallunterscheidungen und uneinheitliche denglische Variablennamen. Behalten habe ich nur die iterative Variante in Python, da sie syntaktisch prägnant ist. --RolandIllig (Diskussion) 15:54, 17. Mai 2023 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: --RolandIllig (Diskussion) 10:28, 29. Okt. 2023 (CET)

Falsche Angabe der Suchschritte unter Komplexität

Im Abschnitt Komplexität ist folgendes angegeben:

Um in einem Feld mit n Einträgen ein Element zu finden bzw. festzustellen, dass dieses sich nicht im Feld befindet, werden maximal \lceil \log_2 n \rceil Schritte benötigt.

Dies ist offensichtlich falsch: Ein Schritt ist wohl die Überprüfung eines Elements. Hat man ein Element, so muss muss man dieses prüfen und es wird ein Schritt benötigt und nicht log_2(1)=0. Auf der englischen Wikipedia Seite ist dafür \lfloor\log_2 N\rfloor+1 angegeben. (nicht signierter Beitrag von 131.234.246.36 (Diskussion) 16:07, 30. Okt. 2015 (CET))

Danke! das ist in der Tat ein Leichtsinnsfehler. Ich korrigier's. --Nomen4Omen (Diskussion) 16:17, 30. Okt. 2015 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: --RolandIllig (Diskussion) 10:29, 29. Okt. 2023 (CET)

Python-Implementierung

Es fehlt noch eine zusätzliche Funktion, so in etwa

def binaersuche(werte, gesucht):
    return binaersuche_rekursiv(werte, gesucht, 0, werte.lastIndex)

als Convenience-Version für den Aufruf. Ich bin aber kein Python-Programmierer, ggf. muss das ein bischen anders lauten. --arilou (Diskussion) 11:14, 18. Dez. 2017 (CET)

Für die Praxis: ja. Für das Verständnis: kein Mehrwert. Also hier einfach weglassen, das ist ja kein Programmier-Handbuch. Chire (Diskussion) 11:14, 21. Dez. 2017 (CET)

Eigentlich denke ich, dass gerade für das Verständnis irgend eine Art 'Anmerkung' benötigt wird, warum die Python-Implementierung plötzlich 4 Aufruf-Parameter benötigt, und wie die beiden zusätzlichen wohl gemeint/Initial zu setzen seien.

Einem alten Programmierer wie mir ist das gleich klar, aber für das Verständnis einer WP-OmA finde ich solch eine zusätzliche Funktion gerade als erheblichen Mehrwert.

Aber (wie gesagt) für korrektes Python kann ich leider nicht sorgen, obige "Implementierung" ist 'Python-fremd erraten'.

--arilou (Diskussion) 12:08, 21. Dez. 2017 (CET)

Stimmt auch nicht ganz. Die vorgestellte Implementierung ist aber noch in ganz anderen Aspekten doof, z.B. die Handhabung von "nicht gefunden". Hier ist die gängige Konvention, einen negativen Index zurückzuliefern, der die Einfügeposition gibt, an der man das fehlende Element einfügen müsste. Genau aus solchen Gründen:

Meiner Meinung nach gehören die Beispiele in konkreten Programmiersprachen sogar ganz raus aus dem Artikel, nur 1x Pseudocode. Für exzessive Beispiele in konkreten Programmiersprachen gibt es ein eigenes Wikibook: b:en:Algorithm Implementation/Search/Binary search Chire (Diskussion) 17:35, 21. Dez. 2017 (CET)

Die Beispiele sind reduziert auf 1* iterative Suche (C anstatt Pseudocode), 1* rekursive Suche (Python anstatt Pseudocode) und 1* rekursiv_funktional (Haskel anstatt Pseudocode).

Mein Vorschlag zur "negativen Rückgabe" wurde abgelehnt.

Beispiele in echten Programmiersprachen wurden gegenüber solchen in Pseudocode präferiert.

Um zum Thema zurückzukommen: Ich finde eine Zusatzfunktion

def binaersuche(werte, gesucht):
    return binaersuche_rekursiv(werte, gesucht, 0, werte.lastIndex)

als zumindest ein Verbesserungsschritt. Dass dabei andere Verbesserungsmöglichkeiten, imo oder gemäß deiner Meinung, (noch) nicht umgesetzt sind - tja, mühsam nährt sich das Eichhörnchen.

--arilou (Diskussion) 09:58, 22. Dez. 2017 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: --RolandIllig (Diskussion) 10:32, 29. Okt. 2023 (CET)

m=0 kann passieren

bzgl. diesem Edit

Basisarray:

idx    0   1   2   3   4
value  7   9  10  12  13

gesucht: '6' , Ablauf:

li   m   re
0         4
     2
0         1
     0
0        -1       Abbruch (hoffentlich! ggf. Überlauf, kein Abbruch!)

--arilou (Diskussion) 13:28, 7. Mai 2019 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von --RolandIllig (Diskussion) 10:34, 29. Okt. 2023 (CET), Ist mittlerweile im Artikel erläutert.

besser verständlicher Code

Hier ein wohl etwas besser verständlicher Code: S= Suchwert / A(...)= Array / P= Position des Suchwertes / N= Anzahl der Werte im Array

XA = 1
XB = N + 1
suchen:
P = XA + Int((XB - XA) / 2)
If S < A(P) Then XB = P : Goto suchen
If S > A(P) Then XA = P : Goto suchen

Der Algorithmus muss in einem Array mit einer Million Werten, maximal nur 20 Werte im Array auslesen, um die Position des gesuchten Wertes zu finden.

Suche nach allen Werten:

Ausgelesene Werte pro Versuch	Trifft in X Fällen zu
1	1
2	2
3	4
4	8
5	16
6	32
7	64
8	128
9	256
10	512
11	1024
12	2048
13	4096
14	8192
15	16.384
16	32.768
17	65.536
18	131.072
19	262.144
20	475.713

Quelle: "teile-und-herrsche"-Suche (Martin Oppermann, September 2008) --77.21.163.85 18:35, 13. Dez. 2020 (CET)

1. Der Code ist kaum anders als jener im Artikel; 'Goto' ist aber aus der Mode.
2. Die Tabelle ist überflüssig, jeder Informatiker kennt die Zweierpotenzen auswendig. Überraschen ist sie dennoch, da der Wert 2^19 falsch ist...

Ich sehe keine notwendige Änderung am Artikel.

--arilou (Diskussion) 10:47, 14. Dez. 2020 (CET)

Es sollte ja auch nur eine Anregung sein.

1. Das der GOTO-Befehl von vielen Leuten nicht gemocht wird, ist mir bewusst.
2. Der Wert 2^19 ist nicht falsch. In der Tabelle stehen die exakten Werte, wie oft es passiert (2. Spalte), dass bei einer Million Werten die entsprechende Anzahl von Zahlen (1. Spalte) gelesen werden mussten. Addiert man alle Werte der 2. Spalte, dann kommt man daher wieder auf die eine Million.

--77.21.163.85 14:41, 14. Dez. 2020 (CET)

Archivierung dieses Abschnittes wurde gewünscht von --RolandIllig (Diskussion) 10:39, 29. Okt. 2023 (CET), Diskussion ist inaktiv, keine Verbesserung des Artikels erkennbar, insbesondere nicht durch die kryptischen Variablennamen XA und XB.

"erweiterte Binäre Suche"

Ich wollte einmal fragen, ob in der Informatik etwas ähnliches wie die "erweiterte Binäre Suche" bekannt ist? Im Jahr 2004 war ich auf die Idee gekommen die Binäre Suche zu verbessern und habe damit die Anzahl der Takte deutlich verringern können, wodurch die gesuchten Positionen teilweise ganz erheblich schneller gefunden werden. Der Algorithmus funktioniert zu Beginn genauso wie die bereits bekannte Binäre Suche: "X" befindet sich am Anfang und "Y" am Ende. Je nachdem ob das Element in der Mitte kleiner oder größer als das gesuchte Element ist, springen dann "X" oder "Y" in die Mitte. Die Erweiterung sieht nun so aus, dass sich "X", wenn es sich nicht auf der gesuchten Position befindet, eine Position nach rechts bewegt. Andernfalls springt "Y" auf die Position "X". Und wenn sich "Y" nicht auf der gesuchten Position befindet, dann bewegt es sich eine Position nach links. Andernfalls springt "X" auf die Position "Y". Die Suche ist dann wie gewohnt beendet, wenn "X" und "Y" identisch sind. Mit dieser Methode werden die gesuchten Positionen insbesondere dann schneller gefunden, wenn sie sich in der unmittelbaren Nähe von "X" oder "Y" befinden. Je nachdem wie und was gesucht werden soll, muss man den Quellcode entsprechend anpassen. --Zahlenzauber (Diskussion) 13:20, 13. Mär. 2024 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: --Zahlenzauber (Diskussion) 23:07, 15. Mär. 2024 (CET)

Pseudocode

WHILE X < Y
M = X + Int((Y - X) / 2)
Wenn Array(M) > Suche
        Y = M
andernfalls
        X = M
Wenn Ende
Wenn Array(X) = Suche
        Y = X
andernfalls
        X = X + 1
Wenn Ende
Wenn Array(Y) = Suche
        X = Y
andernfalls
        Y = Y - 1
Wenn Ende
WHILE Ende

--Zahlenzauber (Diskussion) 16:27, 13. Mär. 2024 (CET)

@Zahlenzauber:Das braucht drei Vergleiche und Speicherzugriffe pro Iteration, das ist schlechter! Eigentlich Grundkenntnis. Speicherzugriffe sind hervorragend geeignet um die Kosten abzuschätzen. Wenn du da wirklich etwas optimieren willst (und deine Daten kleine Primitive sind wie Integer) dann mach eine Cacheline-Optimierung, bei der M auf eine Cacheline "gerundet" wird, und innerhalb dieser Cacheline kann man "für lau" die anderen Werte mit prüfen. --2A02:3100:30DB:FC00:4D01:A17B:D357:B02C 18:09, 13. Mär. 2024 (CET)

Schaue Dir meine Erklärung und den Code bitte noch einmal an. Bei einer Million Positionen benötigt die Binäre Suche 20 Takte und dadurch 20 Vergleiche. Mein Code braucht im besten Fall nur einen Takt und dabei 3 Vergleiche. --Zahlenzauber (Diskussion) 18:40, 13. Mär. 2024 (CET)

Es geht aber nicht um einen Fall, sondern um den Erwartungswert, inkl. negativer Fälle bei denen nichts gefunden wird. Wenn der gesuchte Wert genau in der Mitte ist, ist die binäre Suche zufälligerweise auch schnell fertig - nach nur einem Vergleich... Jetzt nimm doch mal den Fall dass bei einer Million ein Element zwischen position 314159 und 314160 gesucht wird. Und Verwende nicht den Begriff "Takt", weil eine CPU in einem "Takt" keine ganze Schleife durchläuft, sondern ein Vergleich (bspw. bei Strings) viele Takte dauern kann. --2A01:C22:BDAA:7000:4D01:A17B:D357:B02C 07:40, 14. Mär. 2024 (CET)

Die Binäre Suche kann einen Wert aber nicht mit nur einem Vergleich finden, weil man dann ja auch mindestens zwei Vergleiche in der Schleife bräuchte. Bei einer Million Daten braucht die normale Binäre Suche mit nur einem Vergleich immer 20 Durchläufe um eine Position zu finden, weil die Suche erst dann fertig sein kann, wenn der Suchbereich nur noch aus einem Element besteht.

Ich habe zum Beispiel mal eine spezielle Variante von Insertionsort entwickelt, bei der vor dem Verschieben eines Elements, meine "erweiterte Binäre Suche" jedes Mal nach der Endposition sucht. Insertionsort (EBS) ist hier insbesondere bei großen Arrays immer schneller fertig, als das normale Insertionsort, was die Wirksamkeit von meinem Algorithmus bereits ausreichend bestätigt. Hier musste ich zudem sogar vier Vergleiche verwenden, um zu verhindern, dass der "Y"-Vergleich auf die Position vor dem Array zugreift. Der Laufzeit-Vorteil von Insertionsort (EBS) besteht darin, dass das Verschieben der Elemente mit einer einfachen Schleife durchgeführt wird, in der es keine Vergleiche gibt. Die Endposition ist ja schon bekannt.

Da Du zu Beginn von einer "Cacheline" gesprochen hast, muss ich noch einen wichtigen Hinweis hinzufügen: Ich programmiere nur in Basic, PHP und ein wenig in MC-Code auf 8-Bit-Systemen. Letzteres wegen dem Retro-Virus. Meine Ergebnisse sollten aber auf alle Programmiersprachen übertragbar sein, wenn man nichts direkt von einem Prozessor machen lässt und nur mit Programmcode arbeitet. --Zahlenzauber (Diskussion) 12:23, 14. Mär. 2024 (CET)

Natürlich kann eine binäre Suche wenn sie gut implementiert ist mit nur einem Vergleich Glück haben (drei wertiges Veegleichsergebnis)! Bei 1...N wird das Element N getestet, wenn "gleich" hat man ein Ergebnis, andernfalls Rekursion auf 0..N/2-1 oder N/2+1..N. (C=CMP(query, Element[M]); if C==0 return M; if C==-1 usw. - es geht um die Anzahl der potentiell teuren CMP aufrufe!)

Was "ausreichend bestätigt" ist solltest du unabhängigen Analysen überlassen.

P.S. m.E. gibt es Optimalitätsbeweise für die binäre Suche, d.h., du müsstest noch irgendwo einen Fehler in den Beweisen zeigen... Viel Glück, in Wikipedia gehört so eine "Theoriefindung" jedenfalls nicht, solange das nicht in den Lehrbüchern steht... --2A01:C22:C051:9B00:4821:E20B:C93E:2AC3 20:30, 14. Mär. 2024 (CET)

P.S.: https://github.com/openjdk/jdk/blob/87bd6caca03745c21172c3b5e8b0d28724810352/src/java.base/share/classes/java/util/Collections.java#L236 reale Implementierung der binären Suche. Mit "return" wenn das Element getroffen wird. --2A01:C22:C051:9B00:4821:E20B:C93E:2AC3 21:15, 14. Mär. 2024 (CET)

Meine Frage wurde beantwortet. Der Code ist noch nicht bekannt. :Archivierung dieses Abschnittes wurde gewünscht von: --Zahlenzauber (Diskussion) 23:07, 15. Mär. 2024 (CET)

Vergleich zwischen der binären Suche und der Interpolationssuche

Der Beitrag befindet sich hier:

https://de.wikipedia.org/wiki/Diskussion:Interpolationssuche#Vergleich_zwischen_der_bin%C3%A4ren_Suche_und_der_Interpolationssuche

--77.21.163.85 15:30, 14. Dez. 2020 (CET)

Der Autor hatte einen Fehler gemacht, weshalb der Beitrag unzutreffende Ergebnisse enthält. :Archivierung dieses Abschnittes wurde gewünscht von: --Zahlenzauber (Diskussion) 17:17, 16. Mär. 2024 (CET)