#1 29. Januar 2010 Variante der Binärsuche Bin im ersten Semester Informatik, habe folgende Aufgabenstellung: Code: Gegeben: Eine Folge aufsteigend sortierter, unterschiedlicher int-Zahlen. Gegeben als int-Feld a. Gesucht: true, falls ein i mit a[i] = i existiert; false, falls kein solcher Index existiert (i = 0, 1, …) -7 -3 -1 0 1 4 6 8 a) Implementierung, Java (30 Punkte) Implementieren Sie eine rekursive Methode, die obiges Problem löst. Der Zeitaufwand der Methode darf O(log n) nicht überschreiten. Mein Hauptproblem ist es dass ich keinerlei Gedankenansatz habe um diese Aufgabe in O=(log n) zu lösen. Mir ist natürlich vollkommen klar wie die Binärsuche funktioniert. Jedoch scheint mir das nicht viel zu nützen. Habe schon etliche Überlegungen hinter mir, z.B.: Median ermitteln index mit zahl vergleichen und gegebenfalls rechts oder links weiter zu suchen. Jedoch zeigt folgendes Beispiel das dass nichts bringt: Ergebnis auf der Linken Seite weitersuchen 0 1 2 3 4 5 -2 1 3 5 12 19 Ergebnis auf der Rechten Seite weitersuchen 0 1 2 3 4 5 -2 2 3 3 12 19 + Multi-Zitat Zitieren
#2 29. Januar 2010 AW: Variante der Binärsuche mach nen normalisierten binärbaum der bei jedem knoten neben der eigentlichen zahl noch den index vom array speichert. nachdem du dann gleichzeitig den index weist kannste die problemstellung beantworten. + Multi-Zitat Zitieren
#3 30. Januar 2010 AW: Variante der Binärsuche hm verstehe dass beim bessten willen nicht + Multi-Zitat Zitieren
#4 31. Januar 2010 Zuletzt von einem Moderator bearbeitet: 14. April 2017 AW: Variante der Binärsuche schau dir den normalisierten baum an: du musst nurnoch ein a = i finden. wenn der index des elements in der wuzel gleich oder größer ist als die zahl selbst brauchste schonmal nimmer nach links - lässt sich rekursiv auf jeden teilbaum anwenden. mathematisch korrekte beweise liefer ich an dieser stelle nicht. das sagt mir mein bauchgefühl (das sich auch mal irren kann). für mehr hab ich grad keine zeit. + Multi-Zitat Zitieren
#5 31. Januar 2010 AW: Variante der Binärsuche Ich kann dir den source code geben von einer Methode die ich geschrieben habe, mit der man aus einem beliebigen, sortierten Array einen ausgeglichenen Baum erstellen kann. Musst dir dann eben selbst eine Klasse schreiben, in der der Wert und der Arrayindext gespeichert werden. Dann gehst du so vor wie Hardwarehunger sagte. Dann überschreitest du auf keinen Fall O(log(n)), weil der Baum vollständig ausgelgichen ist. greez + Multi-Zitat Zitieren
#6 31. Januar 2010 AW: Variante der Binärsuche mein bauchgefühl sagt mir weiterhin auch dass wenn der index in der wurzel um 2 kleiner ist als die zahl du auch nicht mehr rechst schaun musst, da dort die elemente immer um 1 größer sind und somit kein zahl/index paar die bedingung erfüllen würde. analog geht der "beweis" auch mit dem was ich gestern schon geschrieben habe. die laufrichtung ist also durch die differenz des index zur zahl bestimmt und ist eindeutig. somit haben wir unsere ordnung log n garantiert. nen normalisierten baum aus ner sortierten liste zu erstellen sollte im übrigen kein hindernis sein. immer die mitte der liste als wuzel nehmen. von dieser logische mitte und der daraus resultierenden zwei logischen listen wieder die mitte und links und rechts an den baum hängen ... usw ... + Multi-Zitat Zitieren
#7 31. Januar 2010 AW: Variante der Binärsuche wieso nützt dir die binäre suche nicht viel?!!?!? die binäre suche liegt definitiv in O(log n). (auf wikipedia gibts die binäre suche sogar in der rekursiven variante fertig in java gecodet; sprich: du musst nur von dort abschreiben) ... dass das aufbauen eines "normalisierten" binärbaums (konkret: avl-baum) in O(n log n) liegt. damit ist die aufgabe über einen binärbaum NICHT in O(log n) zu lösen. und der baum generiert sich selbst? womöglich sogar noch in O(1)? + Multi-Zitat Zitieren
#8 31. Januar 2010 AW: Variante der Binärsuche wenn wir dir ordnung als anzahl der vergleiche sehen, wie es zu beginn oft vereinfacht wird, lässt sich von einem sortiertes array mit konstanter ordnung ein normalisierter baum generieren. im übrigen ist die binärsuche auf wiki das gleiche wie hier. nur wir machen vorher nen baum draus. da wir das vergleichen von elementen erst danach machen ist das generieren des baums wie bereits erwähnt von konstanter ordnung. + Multi-Zitat Zitieren
#9 31. Januar 2010 AW: Variante der Binärsuche ok... im falle eines sortierten arrays stimmt das... die frage die ich mir nun stelle: WOZU? da ich ein sortiertes array habe, kann ich doch direkt die binäre suche darauf anwenden und muss nicht erst einen weiteren baum aufbauen... + Multi-Zitat Zitieren
#10 31. Januar 2010 AW: Variante der Binärsuche dann liefer doch mal die lösung anhand ner binären suche. (rhetorisch gemeint) die lösung wie ich so oben beschrieben habe kennste ja. jetzt stellt sich mir nur die frage ob du auch ohne meinen ansatz da oben drauf gekommen wärst. also wozu? um erstmal draufzukommen wann man nach links und wann nach rechts muss + Multi-Zitat Zitieren
#11 31. Januar 2010 AW: Variante der Binärsuche Timer du hast Recht, vor allem weil das Array schon sortiert ist Ich hatte an die Überlegung von Hardwarehunger angeknüpft. Binäre Suche auf ein Arrays gibts 1000x im Netz. greez //naja Hard, so gut waren deine Überlegungen nicht und ob rechts oder links sollte kein problem sein, da in der Aufgabenbeschreibung steht: + Multi-Zitat Zitieren
#12 31. Januar 2010 AW: Variante der Binärsuche naja wenn ich das richtig gegooglet habe waren das mal 30 von 120 punkten bei ner (120 min) klausur im ersten semester. ehrlich gesagt würde ich nur anhand der liste, dem erfolgsdruck und dem zeitdruck auf kein ergebnis kommen. man beachte, dass das eine zeit lang her ist, dass ich sowas das letzte mal gemacht habe + Multi-Zitat Zitieren
#13 31. Januar 2010 AW: Variante der Binärsuche öm... also... ich wusste die antwort auf die aufgabenstellung, nachdem ich mir diese nur durchgelesen habe^^ also wie gesagt: den binärbaum kann man aufbauen, ist aber total unnötig da ein sortiertes array vorliegt. würde kein sortiertes array vorliegen, dann läge die ganze sache in O(n log n): nämlich sortieren mit quicksort (hier: best case - pivotelement teilt das array immer in genau 2 gleich große teile), oder ganz toll: heapsort (da auch im worst case in O(n log n)) und danach eben binärsuche mit O(log n) statt heapsort kann man auch gleich einen balancierten binärbaum aufstellen (z.b. avl-baum): einfügen kann man hier in O(log n), bei n Elementen die eingefügt werden müssen -> O(n log n). suchen kann man dann auch hier in O(log n) + Multi-Zitat Zitieren