Diskussion:Binäre Suche/Archiv/1

aus Wikipedia, der freien Enzyklopädie

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)