Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » n-kleinstes Element über zwei sortierte Arrays
Autor
Universität/Hochschule J n-kleinstes Element über zwei sortierte Arrays
RaffeJos
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 31.07.2021
Mitteilungen: 3
  Themenstart: 2021-07-31

Hallo zusammen! Ich lerne gerade für meine kommende Klausur in Datenstrukturen, Algorithmen und Programmierung und bearbeite dazu ein paar Aufgaben. Ich sitze gerade aber an einer Divide & Conquer Aufgabe fest. https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/54892_SharedScreenshot2.jpg Meine Idee bis jetzt: - Vergleiche mittlere Zahl im Array A mit mittlerer Zahl im Array B - Falls mittlerer Wert in A größer als in B: Mitte der rechten Hälfte von B und Mitte der linken Hälfte von A und vergleiche diese erneut - Falls mittlerer Wert in A kleiner als in B: Mitte der linken Hälfte von B und Mitte der rechten Hälfte von A und vergleiche diese erneut Jedoch ist mir nicht ganz klar, wann ich die Rekursion abbrechen kann bzw. finde ich keine Bedingung, wann eben dieser n-kleinste Wert gefunden ist🤔


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2969
  Beitrag No.1, eingetragen 2021-07-31

Eine binäre Suche wird nicht geeignet sein, das n-te Element zu finden. Du musst eine lineare Suche durchführen. Überlege dir anschaulich, wie du das zweitkleinste Element suchen würdest. Dann verallgemeinere.


   Profil
RaffeJos
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 31.07.2021
Mitteilungen: 3
  Beitrag No.2, vom Themenstarter, eingetragen 2021-07-31

Aber wenn ich eine lineare Suche nutzen würde, so würde ich doch am Ende keine logarithmische Zeit haben, oder? Wie ich bspw. das zeit-kleinste Element finden würde mittels linearer Suche ist mir bewusst, aber dieses Vorgehen würde auch nicht das Teile & Herrsche Prinzip nutzen, oder bin ich da auf einem ganz falschen Weg?


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2969
  Beitrag No.3, eingetragen 2021-07-31

Ich habe das mit log(n) überlesen. Mein Fehler. Wir suchen ein Paar (i,j) mit i+j = n A[i] <= B[j+1] B[j] <= A[i+1] Dann ist max(A[i],B[j]) das gesuchte Element. Das funktioniert mit binärer Suche.


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7085
Wohnort: Milchstraße
  Beitrag No.4, eingetragen 2021-07-31

Hallo RaffeJos, eine interessante Aufgabe! Ich würde wie folgt vorgehen. Schritt 0: Setze ma = mb = 1, Ma = Mb = n. Schritt 1: Wir wissen bereits, dass entweder a[i] für ein i aus ma, ma+1, ..., Ma der n-kleinste Wert ist, oder dass b[j] für ein j aus mb, mb+1, ..., Mb der n-kleinste Wert ist. Fall 1: ma = Ma und mb = Mb. Stopp. Fall2: (sonst) Setze jetzt ta = runden((ma + Ma)/2), tb = n - ta. Wenn a[ta] < b[tb], setze ma = ta und Mb = tb. Wenn a[ta] > b[tb], setze Ma = ta und mb = tb. Gehe zu Schritt 1. [Die Antwort wurde vor Beitrag No.1 begonnen.]


   Profil
Kitaktus
Senior Letzter Besuch: im letzten Monat
Dabei seit: 11.09.2008
Mitteilungen: 6879
Wohnort: Niedersachsen
  Beitrag No.5, eingetragen 2021-07-31

Ein offensichtlicher Teile-und-Herrsche-Ansatz: Nimm die beiden mittleren Elemente $a_i$ und $b_i$ und vergleiche sie. O.B.d.A. sei $a_i$ der größere Wert. Ist $2i\geq n$, dann sind die Elemente $a_{i+1},...,a_n$ auf jeden Fall zu groß. Ist $2i


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2969
  Beitrag No.6, eingetragen 2021-08-01

Ich habe obigen Ansatz mal naiv implementiert. \sourceon Python \numberson def search(A,B,n): lo, hi = 0, len(A)-1 # TODO: Handle potential IndexOutOfRange while 1: m = (lo + hi) // 2 if A[m] >= B[n-m-1] and A[m] <= B[n-m]: return A[m] if A[m] <= B[n-m-1] and A[m+1] >= B[n-m-1]: return B[n-m-1] if A[m] >= B[n-m-1] and A[m] >= B[n-m]: hi = m else: lo = m return None \sourceoff Die Spezialfälle zu behandeln ist im Sinne der Aufgabenstellung kein Problem, da man ja garantiert, dass jedes Array mindestens n Elemente enthält. Ohne diese Voraussetzung wird es ein wenig hässlicher.


   Profil
RaffeJos
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 31.07.2021
Mitteilungen: 3
  Beitrag No.7, vom Themenstarter, eingetragen 2021-08-01

Danke für eure Hilfe!! Ich habe jetzt einen Pseudocode gefunden und habe das Prinzip hinter Aufgabe auf jeden Fall verstanden. Auch wenn ich finde, dass diese Aufgabe nicht ganz einfach ist😄


   Profil
RaffeJos hat die Antworten auf ihre/seine Frage gesehen.
RaffeJos 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]