Diskussion:Binäre Suche

Auf dieser Seite werden Abschnitte ab Überschriftebene 2 automatisch archiviert, die seit 14 Tagen mit dem Baustein {{Erledigt|1=--~~~~}} versehen sind. Die Archivübersicht befindet sich unter Archiv.

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)

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)

Binäre Suche#Erwartungswert der Komplexität

Überschrift und Zweck des genannten Abschnitts sind mir etwas rätselhaft:

1. IMHO gibt es einen Erwartungswert von asymptotischen Größen (»Komplexität«, O-Notation) nicht. Allenfalls einen Erwartungswert (≈ Mittelwert) für die Anzahl der Suchschritte.
2. Wenn als Ergebnis nur ${\mathcal {O}}(\log \ n)$ herausgearbeitet werden soll, dann ist das anderswo einfacher und direkter erledigt und der Formelkram unnötig.
3. Dass die Suchmenge immer 2ⁿ Elemente enthält, ist bei einem derartigen Rechenaufwand eine unzulässige Vereinfachung.
4. Es fehlt eine Angabe, woher die ganze Überlegung und Rechnung stammt.

--Nomen4Omen (Diskussion) 17:03, 2. Nov. 2015 (CET)

lieber Nomen4Omen, ich muss dir teilweise widersprechen:

1. Ich gebe dir recht, da müsste die Überschrift heißen 'Erwartungswert der Anzahl der Abfragen'
2. Die durchschnittlichen Kosten können durchaus kleiner sein als die Komplexität als maximale Kosten. In diesem Falle ist es nicht der Fall, musste aber gezeigt werden.
3. Du hast offenbar den Beitrag nicht richtig gelesen, denn dort wurde angenommen dass die Suchmenge kleiner oder gleich als eine Potenz von 2 ist.
4. Die Überlegung stammt von jemand der sich auch mal für den Durchschnitt der Suchkosten interessiert, in diesem Falle von mir. Die dort verwendete Rechnung dürfte wohl nachvollziehbar sein.

--Ym0510 (Diskussion) 3. Jan. 2016 (CET) (14:38, 3. Jan. 2016 (CET), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

@Ym0510

1. Wie ich mit dem Hinweis auf Erwartungswert (den Du ja eigentlich selbst schon drin hast) ausdrücken wollte, hat dieser mit Verteilungen zu tun. Und ohne eine Annahme über diese ist Deine Aussage falsch, da es Verteilungen gibt, bei denen eine von der Mächtigkeit der Suchmenge unabhängige Komplexität herauskommt. Beispiel: Zugriffswahrscheinlichkeit auf Element_i = 2^-i. Dann dominiert nämlich das erste Element die ganze Komplexität, so dass ≈ ½ herauskommt. (Allerdings sind bei diesem Beispiel die maximalen Kosten dann proportional.)
2. Erster Satz ist richtig. Zweiter Satz ist falsch: siehe 1.
3. Dass die Suchmenge kleiner oder gleich als eine Potenz von 2 ist, ist (zwar sprachlich falsch, aber) arithmetisch immer richtig. Im betroffenen Abschnitt habe ich einen Nachweis für $C(N)\leq C(2^{n})$ nicht gesehen. (Zugegeben: Ich hab's gar nicht richtig gelesen, weil ich schon Deine Annahme $P(\omega _{1})={\frac {1}{2^{n}}}$ nicht verstanden habe bzw. mir falsch vorkam. Siehe auch 1., wo bei mir $P(\omega _{1})={\frac {1}{2}}$ herauskommt.)
4. Wikipedia:Belege und WP:OR erwarten zuverlässige Belege.

--Nomen4Omen (Diskussion) 15:38, 3. Jan. 2016 (CET)

@Nomen4Omen

1. Wenn du den Beitrag gelesen hättest, hättest Du gesehen dass in der dort definierten Rekursion die Annahme der Gleichverteilung bereits enthalten ist.
2. Sowohl erster als auch zweiter Satz ist richtig, siehe 1.
3. Wenn du den Beitrag gelesen hättest dann hättest gesehen dass dort die Formulierung 'für $N\leq 2^{n}$ ' steht, also $N$ und $n$ sind so dass die Ungleichheit gilt. Ebenso hättest du gesehen dass genau $C(N)\leq C(2^{n})$ gezeigt wurde. Es sieht so aus dass du hier Wahrscheinlichkeit und Komplexität durcheinander bringst: in deinem Punkt 1. oben schreibst du die Zugriffswahrscheinlichkeit aus $2^{i}$ Elementen ist $2^{-i}$ und die Komplexität 1/2. Hier behauptest du die Zugriffswahrscheinlichkeit aus $2^{n}$ Elementen wäre 1/2. Ich empfehle dir den Beitrag zu lesen, bevor du mit mir darüber diskutierst, denn ich habe langsam keine Lust den ganzen Beitrag hier wiederzugeben.

1. Mit Hinweis auf Reihe Mathematik sind die nötigen Referenzen erbracht. Mitdenken muss man etwas auch wenn man so etwas verstehen will.

Ym0510 (Diskussion) 12:16, 5. Jan. 2016 (CET)

@Ym0510
Ich habe Deinen alten Beitrag vorliegen, und Du musst ihn nicht wiederholen.
Zu 1a: In Deinem 2. Satz im besagten Beitrag steht: „Die Wahrscheinlichkeit das Suchargument aus ... zu finden ist dann ...“. Das lese ich als eine Schlussfolgerung und nicht so, dass Du damit die Gleichverteilung voraussetzst. Und ich sehe nicht, wo Du diese sonst vorausgesetzt haben willst. Wenn Du vom Leser verlangst, dass er in Deiner „dort definierten Rekursion die Annahme der Gleichverteilung bereits“ erkennt, verlangst Du zu viel von ihm. Ich habe Dich niemals so gelesen. Ein Begriff «Gleichverteilung», «Gleichverteiltheit» oder «gleichverteilt» kommt in Deinem Text nicht vor, denn beim Suchen mit der Browser-Suchfunktion auf «leichv» sagt der: «Keine Übereinstimmung.»
(Aber auch jetzt, wo ich erkenne, dass Du es gleichverteilt gemeint hast, mag ich nicht akzeptieren, dass für den Beweis von »gleichverteilter Durchschnitt verhält sich asymptotisch nicht besser als gleichverteilter worst case« solcher Formelkram erforderlich sein soll.)
Zu 3: Mein Beispiel einer extremen Ungleichverteilung in meinem Punkt 1. vom 3. Jan. 2016 mit einem beschränkten Mittelwert (d.h. wesentlich besser als der worst case) für die Suchschritte (unabhängig von der Anzahl der Elemente) ist nicht vollständig. Angesichts des riesigen Missverständnisses über die Gleichverteilung ist wohl überflüssig, es in Ordnung zu bringen. --Nomen4Omen (Diskussion) 15:19, 5. Jan. 2016 (CET)

@Nomen4Omen
Ich verstehe nicht dass ein Missverständnis das durch den Zusatz "...bei Annahme von Gleichverteilung...' behoben werden kann ein riesiges sein soll. Zumal wenn man die Rekursion sieht sofort erkennt dass dies eine Gleichverteilungsannahme ist. Du bist natürlich nicht darauf gekommen weil Du es nicht gelesen hast.

"(Aber auch jetzt, wo ich erkenne, dass Du es gleichverteilt gemeint hast, mag ich nicht akzeptieren, dass für den Beweis von »gleichverteilter Durchschnitt verhält sich asymptotisch nicht besser als gleichverteilter worst case« solcher Formelkram erforderlich sein soll.)".

Erstens ist diese Formulierung nicht korrekt da der Begriff worst case von seiner Definition her keiner w-Verteilung unterliegt - sonst wäre er ja kein worst case - so dass sie korrekterweise heißen müsste 'der erwartungswert unter Gleichverteilungsannahme ist gleich aufwendig wie der worst case Fall'. Somit zweitens die Frage an Dich: wie würdest Du diese Aussage ohne den 'Formelkram' zeigen?

--Ym0510 (Diskussion) 16:47, 9. Jan. 2016 (CET)

@Ym0510
Es ist schon ein starkes Stück: Am 13.01.2013 hast Du Deinen Beitrag Binäre Suche#Erwartungswert der Komplexität veröffentlicht. Kein Wort von Gleichverteilung, nur Formelkram und der ach so hilfreiche Hinweis „(s. auch Reihe (Mathematik))“, der dazuhin als Beleg für den Formelkram herhalten soll. Ziemlich genau 3 Jahre später und nachdem Du in der Enge bist, blaffst Du zurück, dass es sich um eine Gleichverteilung handelt und dass man die hätte erahnen können, wenn man Deinen Formelkram gelesen hätte. Nach all diesem beharrst Du darauf, dass dies keine grobe Irreführung war, sondern dass das Missverständnis durch den Zusatz "...bei Annahme von Gleichverteilung...' hätte behoben werden können. Ein starkes Stück fürwahr. (Am Ende würde es mich nicht wundern, wenn Du triumphierend verkünden würdest, dass das alles eine riesige Verarsche war.)
Dabei ist das Ganze sehr einfach: Die binäre Suche im Array läuft – wie unter #Algorithmus beschrieben – völlig determiniert ab. Der einzige Freiheitsgrad ist der, ob man bei der Mittelwertbildung der Indices, wenn die Summe nicht durch 2 teilbar ist, nach unten oder nach oben rundet (was aber am Laufzeitverhalten nichts ändert). Wenn man dieses Verfahren in einem binären Entscheidungsbaum abbildet, erhält man einen sog. vollständigen Binärbaum. Das ist einer, bei dem jede Ebene bis auf die unterste voll ist. Im Artikel Binärer Suchbaum#Suchtiefen und Pfadlängensummen wird die Anzahl der Vergleiche ${\underline {S}}_{\mathfrak {e}}(n)$ für alle Pfade von der Wurzel bis zu jedem Knoten im Baum – das ist die dortige Zugriffsverteilung ${\mathfrak {e}}$, bei der alle Knoten gleich wahrscheinlich sind – gegeben durch ${\underline {S}}_{\mathfrak {e}}(n)=1+(n+1)k-2^{k}$ mit $\scriptstyle 2^{k-1}\leq n+1\leq 2^{k}$. Für den Mittelwert muss man ${\underline {S}}_{\mathfrak {e}}(n)$ nur noch durch $n$ dividieren. --Nomen4Omen (Diskussion) 21:57, 10. Jan. 2016 (CET)

Kriegt Euch mal wieder ein. Ohne (starke) Annahmen gibt es kein Ergebnis. Die mittlere Pfadlänge im Binärbaum betrifft nur die erfolgreiche Suche, und nimmt (Mittelwert!) an dass alle Elemente gleich oft gesucht werden. Ändern wir die Annahme wie die Suchen verteilt sind ab, und suchen wir immer den Median (bei ungerader Anzahl), so bekommen wir O(1) als Suchzeit! Das reale Suchverhalten wird also irgendwo dazwischen liegen. Deswegen: Keine Beweise auf Wikipedia führen (Theoriefindung), sondern Primärquellen verlinken. (nicht signierter Beitrag von 91.52.13.120 (Diskussion) 11:45, 11. Jan. 2016 (CET))

@91.52.13.120 mit dem letzten Hinweis darüber wie die Natur eines Beitrags in Wikipedia sein sollte kann ich jedenfalls mehr anfangen als mit dem letzten Einwurf (des bisherigen Diskutanten) dessen erster Teil außer Polemik nichts zur Sache beiträgt und kein Bisschen Beachtung verdient und dem zweiten Teil der meint dass der naive Kram dort mehr wert sein soll als der Formelkram.

--Ym0510 (Diskussion) 16:47, 9. Jan. 2016 (CET)

@Ym0510
Wirklich mein letztes Wort in dieser Sache: Oben, in Deinem Beitrag vom 14:38, 3. Jan. 2016 schreibst Du: „Die durchschnittlichen Kosten können durchaus kleiner sein als die Komplexität als maximale Kosten. In diesem Falle ist es nicht der Fall, musste aber gezeigt werden.“ In Deinem Beitrag vom 13.01.2013 schreibst Du aber nur etwas von „Erwartungswert von $C(N)\leq ...=2n+{\frac {1}{2^{n}}}$ und somit wieder von der Komplexitätsklasse ${\mathcal {O}}(\log \ n)$.“
Im Verstehen, wie Du mit einer solchen Ungleichung gezeigt haben willst, dass die durchschnittlichen Kosten nicht kleiner sind als die maximalen Kosten, da scheitere ich abgrundtief. --Nomen4Omen (Diskussion) 20:57, 20. Jan. 2016 (CET)
Nachtrag: Ach ja, nicht einmal bei der Wahl der Variablennamen scheinst Du aufzupassen: Kommt im Zitat hier $n$ doch in zwei völlig verschiedenen Bedeutungen vor! --Nomen4Omen (Diskussion) 11:03, 21. Jan. 2016 (CET)

Fehler in der Grafik "Binary search into array.svg"

Wieso wird in der ersten Verzweigung G < L geprüft? Es müsste doch G < J geprüft werden.

Danke für den Hinweis. Ist korrigiert! --Nomen4Omen (Diskussion) 11:23, 21. Sep. 2017 (CEST)

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)

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)

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)

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)