Matroids Matheplanet Forum Index
Moderiert von matph
Informatik » Programmieren » Binäre Suche
Autor
Universität/Hochschule J Binäre Suche
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 416
  Themenstart: 2021-09-23 10:58

Angenommen, ich hätte alle Primzahlen vorliegen 1 bis 101 vorliegen. \sourceon php $prim = array (1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101 \sourceoff Ist 9 ne Primzahl? Ich schreibe eine Rekurion. function IsPrime=__binary_search(Prim, links, rechts, nummer). Prim ist das Feld oder array, nummer ist die zu untersuchende Zahl, links und rechts die boundaries, davon ausgehend, das die untersuchte Zahl <= maxprim hier 101 ist Ich fange an mit links =0 als index in das erste Elemment von array Prim Das 0te element ist 1. Das grösste maxprim 101 hat den maxindex 26. links = 1, rechts = 101. Mitte ist = $\displaystyle\frac {Prim[0]+ Prim[26]}{2} =51$. $\displaystyle 9 \lt 51$ Also ist das neue links=1, rechts = 51. __binary_search($Prim, $1,51,9) 51 > 9 Mitte ist 26. 9<26. links=1,rechts = 26. $\displaystyle\frac {Prim[0]+ 26}{2} =13$. Mitte ist = $\displaystyle\frac {Prim[0]+ 13}{2} =7$. 7 <9 also: __binary_search(Prim, 7,9,9). Es ist das rechte Element die untersuchte Zahl, was aber kein Abbruchriterium ist, oder? Mitte ist = $\displaystyle\frac {7+ 9}{2} =8$. 8<9. __binary_search(Prim, 8,9,9) Mitte ist = $\displaystyle\frac {8+ 9}{2} =8,5$. und da weiß ich nicht mehr weiter... Ignorieren wir die Nachkommsstellen wie 8..5 mittels floor[8,5] so kommen wir immer wieder auf __binary_search(Prim, 8,9,9). Wenn wir floor nicht anwenden auf __binary_search(Prim, 8.5,9,9) dann __binary_search(Prim, 8.75 ,9,9) __binary_search(Prim, 8.825 ,9,9)ad infinitum, was keinen Sinn macht. Man könnte auch bei so kleinen Suchgruppen wie oben mit inarray(prim,9) arbeiten, was aber laufzeitmaessig unertraeglich wird. Mit 1..9999991 haben wir schon 664573 Primzahlen abzusuchen, da ist natürlich isPrime() = __binary_search($Prim, 1,9999991) besser. Test mal 2405737 auf Primalität. Ich verstehe aber das Abbruchkrterium nicht. Danke


   Profil
Elli_2001
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2021
Mitteilungen: 7
  Beitrag No.1, eingetragen 2021-09-23 11:16

Hallo juergenX, für eine untere Grenze $i$ und obere Grenze $j$ schreibst du: $\frac{Prime[i]+Prime[j]}{2}$ aber ich glaube es sollte $\frac{i+j}{2}$ heißen. Also z.B. im ersten Fall, i=0, j=26: $\frac{0+26}{2} = 13$ $Prime[13] = 41 > 9$ Also wird jetzt die obere Grenze angepasst. Das heißt, jetzt untersuchst du: $j := \frac{0+13}{2} = 6,5$ Hier kannst du z.B. aufrunden auf 7 oder auch abrunden auf 6, das sollte egal sein, hauptsache du bleibst konsistent. Also z.B. $6$. Das Abbruchkriterium ist, wenn $i \geq j$. Grüße, Elli


   Profil
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 416
  Beitrag No.2, vom Themenstarter, eingetragen 2021-09-23 13:41

\quoteon(2021-09-23 11:16 - Elli_2001 in Beitrag No. 1) Hallo juergenX, für eine untere Grenze $i$ und obere Grenze $j$ schreibst du: $\frac{Prime[i]+Prime[j]}{2}$ aber ich glaube es sollte $\frac{i+j}{2}$ heißen. Also z.B. im ersten Fall, i=0, j=26: $\frac{0+26}{2} = 13$ $Prime[13] = 41 > 9$ Also wird jetzt die obere Grenze angepasst. Das heißt, jetzt untersuchst du: $j := \frac{0+13}{2} = 6,5$ Hier kannst du z.B. aufrunden auf 7 oder auch abrunden auf 6, das sollte egal sein, hauptsache du bleibst konsistent. Also z.B. $6$. Das Abbruchkriterium ist, wenn $i \geq j$. Grüße, Elli \quoteoff Ok so weit so gut ...;) \sourceon nameDerSprache 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101 0, 1, 2, 3, 4, 5, 6, 7 ,8 ,9 ,10 ,11 ,12 ,13 ,14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 ,26 \sourceoff Ist 9 in diesem Feld? Nach abrunden suche in den Werten, nicht den indizes 0,13. Im weiteren nur abrunden: mitte $6, 13 = 9,5 \equiv 9$ mitte $6, 9 = 7,5 \equiv 7 \in prime$ mitte $7, 9 = 8 \not\in prime$ mitte $8, 9 = 8 \not\in prime$ mitte $8, 8 = 8 \not\in prime$. Was "wissen" wir jetzt? oder aufrunden mitte $6, 13 = 9,5 \equiv 10$ mitte $6, 9 = 7,5 \equiv 8$ mitte $8, 9 = 9\not\in prime$ mitte $9, 9 = 9\not\in prime$ Anscheinend ist links = rechts in beiden , aber Fällen was folgt daraus? $\not\in prime \lor \in prime$ weiß ich eben, aber das isr nur ne Anmerkung. ( Mit Indizes zu arbeiten: mitte $3, 6 = 4 ,p[4] =7$ mitte $4, 6 = 5 ,p[5] =11$ mitte $4 ,5 = 4 ,p[4] =7$ mitte $p[4} ,p[5] = 9$ mitte $p[4} ,p[4] = 7$ mitte $p[5} ,p[5] = 11$ fuehrt uns nicht weiter... ) Nehmen wir 11. Wir wissen zwar das es sich um eine Prime handelt nicht, hoffen also, dass sie im PrimFeld vorkommt. abrunden: mitte $0,101 = 50$ mitte $0,50 = 25\not\in prime$ mitte $0,25 = 12\not\in prime$ mitte $0,12 = 6\not\in prime$ mitte $6,12 = 9\not\in prime$ mitte $9,12 = 10\not\in prime$ mitte $10,12 = 11 \in prime$ mitte $11,12 = 11 \in prime$ mitte $11,11 = 11 \in prime$ also links =rechts, Abbruch, aber mit welchem Ergebnis? links = rechts in beiden Fällen,aber daraus folgt was? Zusätzlich muss links = rechts $\in prime$ sein. Aber das wissen wir ja nicht, wollen es ja rausfinden. Der Algorithmus endet immer in l=r. Einen Fall l>r kann man kaum finden oder? Einen Fall lgehört das auch eher in das Programmierforum. \sourceon php function isPrime ($links,$rechts,Nummer) while ($links<$rechts) { vergleiche nummer mit links und rechts; Trenne auf; } $Ergebnis = boolean; \sourceoff


   Profil
Elli_2001
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2021
Mitteilungen: 7
  Beitrag No.3, eingetragen 2021-09-23 15:10

Hallo juergenX, leider ist es etwas schwierig deiner Notation zu folgen, da sie anders aussieht als im ersten Beitrag. Ich versuche trotzdem mal deine Fragen zu beantworten: 1. Wenn die Abbruchbedingung erreicht ist, also $i \geq j$ mit $i$ als untere Grenze (links) und $j$ also obere Grenze (rechts), das Element bis dahin aber nicht gefunden wurde, dann ist das Element nicht in der Liste. In deinem ersten Fall suchst du die 9, diese wird aber nicht gefunden. Das liegt daran, dass $i=j=4$ oder $i=j=5$ je nach dem ob man aufrundet oder nicht. Du weist also, dass sich zwischen den Zahlen $Prime[4]=7$ und $Prime[5]=11$ keine Zahl befindet. Da laut Voraussetzung die Liste sortiert ist, kann $9$ nicht in der Liste enthalten sein. Also gilt $9 \notin Prime$. 2. Der Grund weshalb man das arithmetische Mittel bzgl den Indizes und nicht Werten berechnet, liegt daran, dass man nicht weiß wie die Werte der Liste steigen. In deinem Fall steigen die Zahlen in etwa linear. Betrachte aber mal die folgende Liste: $L = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]$ Jetzt suchen wir nach der 3 und rechnen mit deiner Methode (arithmetisches Mittel bzgl den Werten). Dann würdest du rechnen: $\frac{Prime[0]+Prime[10]}{2}=512,5$ Also musst du weiter nach links und es ergibt sich: $\frac{Prime[0]+Prime[9]}{2}=256,5$ Vielleicht merkst du es schon. Wir wandern jetzt so lange genau ein Element von links nach rechts, bis $i=j=1$. Somit kommen wir auf eine Worst Case Laufzeit von $\mathcal{O}(n)$. Das Bisektionsverfahren verspricht aber $\mathcal{O}(log(n))$. Bei den Indizes wissen wir, dass sie linear aufsteigend sortiert sind. Da kann uns sowas also nicht passieren. Grüße, Elli


   Profil
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 416
  Beitrag No.4, vom Themenstarter, eingetragen 2021-09-23 20:48

OK jetzt hab ichs glaub ich. Nach der 9 suchen bringt p[4]= 7, p[5]=11 Die mitte ist n=9 was verwirrt ;) Ein Mittelindex gibt es nicht. Daher 9 is not in that field. Insofern muss das Kriterium gelten: zwischen benachbarten Indizes l=p[x] , r =p[x+1] kann n nicht liegen, auch nicht 8,9,10 da diese gar nicht im Feld liegen, was wir aber nicht unbedingt wissen muessen oder. Liegen zwischen 997813 und 997877 noch Primzahlen? Dann nicht, wenn sie benachbarte Indizes haben. Denen wir uns mit der Binaersuche nähern. Das meinst du wohl mit binary_search mit dem benchmark oder wie sagt man $\mathcal{O}(log(n))$ ist wohl das beste in sortierten Feldern. In Deiner $L = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]$ ist L[0]=1, L[1]=2, L[2]=4, können wir die 3 suchend bei indizes 1 und 2 und abbrechen.


   Profil
Elli_2001
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2021
Mitteilungen: 7
  Beitrag No.5, eingetragen 2021-09-23 22:06

\quoteon(2021-09-23 20:48 - juergenX in Beitrag No. 4) [...], was wir aber nicht unbedingt wissen muessen oder. \quoteoff Genau, wir müssen nicht wissen welche Zahlen fehlen. Wir könnten uns aber einfach die zwei Ränder ansehen, also 7 und 11, und daraus schließen, dass alle Zahlen dazwischen fehlen. Gleiches Argument wie oben. \quoteon(2021-09-23 20:48 - juergenX in Beitrag No. 4) Liegen zwischen 997813 und 997877 noch Primzahlen? \quoteoff Im offenen Intervall ]997813, 997877[ liegen keine Primzahlen, aber die zwei genannten Zahlen sind Primzahlen. Quelle \quoteon(2021-09-23 20:48 - juergenX in Beitrag No. 4) Das meinst du wohl mit binary_search mit dem benchmark oder wie sagt man $\mathcal{O}(log(n))$ ist wohl das beste in sortierten Feldern. In Deiner $L = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]$ ist L[0]=1, L[1]=2, L[2]=4, können wir die 3 suchend bei indizes 1 und 2 und abbrechen. \quoteoff Ich kenne es nur unter dem Namen "O-Notation" oder "Landau-Symbol". Dabei bezeichnet $\mathcal{O}(f(n))$ eine Menge, die alle Funktionen enthält, die bis auf eine Konstante langsamer wachen als die Funktion f. Das waren meine eigenen Worte. Mehr und genaueres findest du hier. \quoteon(2021-09-23 20:48 - juergenX in Beitrag No. 4) $\mathcal{O}(log(n))$ ist wohl das beste in sortierten Feldern. \quoteoff Genau. In unsortierten Feldern fällt mir nur die naive Suche ein, d.h. von vorne bis hinten durchlaufen und jedes Element ansehen => Mit einer Listenlänge von $n$, benötigt man $\mathcal{O}(n)$ Zeit. Grüße, Elli


   Profil
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 416
  Beitrag No.6, vom Themenstarter, eingetragen 2021-09-24 07:33

Ich bedanke mich abschliessend bei Dir, Elli. Bin nebenbei auch immer wieder angenehm überrascht, wie schnell die sort Routinen in php sind wahrscheinkich Quicksort? Aber brauchen wir nicht diskutieren 😃😄🙄👍


   Profil
juergenX hat die Antworten auf ihre/seine Frage gesehen.
juergenX hat selbst das Ok-Häkchen gesetzt.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]