Rekursive Suche in einem Feld

M

marvpaul

Mitglied
Hallo, will eine rekursive Methode zum durchsuchen eines Feldes schreiben. Wie die Suche funktioniert ist erstmal relativ nebensächlich, mir geht es nur darum das in der Main-Methode erzeugte Feld auch in der Such-Methode nutzen zu können. Mein Quellcode schaut so aus:
Java:
package rekursivesuche;

public class rekursivesuche {	

	public static void main(String[] args){
	int suche = 8;
	int zahlenfeld[] = {5, 3, 6, 8, 1, 8, 8, 7, 5, 3, 0, 1};//Zahlenwert erzeugen
	//sortieren
	int hilfe; //Zwischenspeicher beim Tauschen
	 for (int j = 0; j < zahlenfeld.length-j; j++){ 
		 for (int i = 0; i < zahlenfeld.length-1; i++){ //Durchlauf des Feldes - Abstand
			 if (zahlenfeld[i] < zahlenfeld[i+1]){ //Wenn Vorgänger größer ist dann wird getauscht --> Am Ende des Durchlaufs kleinste Zahl an zahlenfeld.length-j
				 hilfe = zahlenfeld[i]; //Tausch
				 zahlenfeld[i] = zahlenfeld[i+1];
				 zahlenfeld[i+1] = hilfe;
			 } 
		 } 
	 }
	 for (int i = 0; i < zahlenfeld.length; i++){ //Durchlauf des Feldes
		 System.out.print(zahlenfeld[i] + " "); //Ausgabe der Feldvariablen 
	 }
	 suche();
	}
	public static void suche(){
		//Mittelwert des Arrays bilden
		int l = 0;
		int r = zahlenfeld.length;
		int m = (l + r)/2;
		if(zahlenfeld[m] == suche) 
			return zahlenfeld[];
				
		
	}
}

Problem ist: In der Methode suche ist das zahlenfeld nicht mehr bekannt, wie kann ich mein Feld methodenübergreifend deklarieren?
 
M

marvpaul

Mitglied
Java:
package rekursivesuche;

public class rekursivesuche {	

	public static void main(String[] args){
	int suche = 8;
	int zahlenfeld[] = {5, 3, 6, 8, 1, 8, 8, 7, 5, 3, 0, 1};//Zahlenwert erzeugen
	//sortieren
	int hilfe; //Zwischenspeicher beim Tauschen
	 for (int j = 0; j < zahlenfeld.length-j; j++){ 
		 for (int i = 0; i < zahlenfeld.length-1; i++){ //Durchlauf des Feldes - Abstand
			 if (zahlenfeld[i] < zahlenfeld[i+1]){ //Wenn Vorgänger größer ist dann wird getauscht --> Am Ende des Durchlaufs kleinste Zahl an zahlenfeld.length-j
				 hilfe = zahlenfeld[i]; //Tausch
				 zahlenfeld[i] = zahlenfeld[i+1];
				 zahlenfeld[i+1] = hilfe;
			 } 
		 } 
	 }
	 for (int i = 0; i < zahlenfeld.length; i++){ //Durchlauf des Feldes
		 System.out.print(zahlenfeld[i] + " "); //Ausgabe der Feldvariablen 
	 }
	 suche(zahlenfeld[]);
	}
	public static void suche(int zahlenfeld[]){
		//Mittelwert des Arrays bilden
		int l = 0;
		int r = zahlenfeld.length;
		int m = (l + r)/2;
		if(zahlenfeld[m] == suche) 
			return zahlenfeld[];
				
		
	}
}

Wie denn? Hab es so hier probiert und das geht nicht!
 
G

Gucky

Top Contributor
Die eckigen Klammern sind nur für Zugriffe auf Elemente des Arrays. Wenn du das ganze Array übergeben willst, so musst du sie weg lassen.
 
njans

njans

Top Contributor
Siehe gucky

Ebenso:
Gewöhne dir gleich an aus
Java:
public static void suche(int zahlenfeld[])
Das zu machen:
Java:
public static void suche(int[] zahlenfeld)

Array-Klammern sind Teil des Typs nicht des Namens.
 
G

Gucky

Top Contributor
Dazu noch kurz: Dem Compiler ist es egal aber die erste Schreibweise ist schwerer zu lesen und "grammatikalisch" falsch.
 
A

arilou

Bekanntes Mitglied
Dein Sortieralgorithmus ist ein (leicht modifizierter) Bubblesort.
Dazu: Es ist unschön, während eines for-Schleifenlaufs an der Endbedingung herumzudrehen.
Bei dir läuft die Schleife bis (zahlenfeld.length-j), was sich aufgrund sich änderndem j bei jedem Durchlauf ändert.
Dadurch kann der Compiler den Code nicht optimieren; besser du wählst als Laufbedingung gleich
j < (zahlenfeld.length / 2)
, das bleibt immer derselbe Wert. (Und ist obendrein falsch, denn Bubblesort hat worst case = n(n-1)/2, aber das /2 müsste im inneren Schleifenzähler i anschlagen, und nicht außen bei j.)

Anders gesagt:
Bei manchen Wert-Anordnungen sortiert dein "Sortieralgorithmus" nicht korrekt.
 
Zuletzt bearbeitet:
M

marvpaul

Mitglied
Danke Leute, ihr habt mir sehr geholfen. Habe jetzt auch mitbekommen das mein Bubblesort falsch sortiert und dementsprechend das -j rausgenommen, heißt also so hier: for (int j = 0; j < zahlenfeld.length; j++), das geht m.A.n. auch.

Habe jetzt auch weiter an der Suche gearbeitet und es klappt soweit. Leider bekomme ich es nicht hin ihn bis zum Ende des Feldes laufen zu lassen wenn ich die Methode rekursiv gestalte bzw habe keine passende Abbruchbedingung gefunden und das ganze endet mit einem out of bounds. Mein Quellcode mit der Suche (sicher nicht optimal) bis zu EINEM passendem Wert schaut so aus:

Java:
package rekursivesuche;

public class rekursivesuche {	

	public static void main(String[] args){
	int suche = 8;
	
	int zahlenfeld[] = {5, 3, 6, 8, 1, 8, 8, 7, 5, 3, 0, 1};//Zahlenwert erzeugen
	int l = 0; //"Linkes Ende" des Arrays
	int r = zahlenfeld.length; //"Rechtes Ende" des Arrays
	int m = (l + r)/2; //"die Mitte" des Arrays 
	//sortieren
	
	int hilfe; //Zwischenspeicher beim Tauschen
	 for (int j = 0; j < zahlenfeld.length; j++){ 
		 for (int i = 0; i < zahlenfeld.length-1; i++){ //Durchlauf des Feldes - Abstand
			 if (zahlenfeld[i] > zahlenfeld[i+1]){ //Wenn Vorgänger größer ist dann wird getauscht --> Am Ende des Durchlaufs kleinste Zahl an zahlenfeld.length-j
				 hilfe = zahlenfeld[i]; //Tausch
				 zahlenfeld[i] = zahlenfeld[i+1];
				 zahlenfeld[i+1] = hilfe;
			 } 
		 } 
	 }
	 for (int i = 0; i < zahlenfeld.length; i++){ //Durchlauf des Feldes
		 System.out.println(zahlenfeld[i] + " "); //Ausgabe der Feldvariablen 
	 }
	 suche(zahlenfeld, suche, m, r, l);
	}
	public static void suche(int zahlenfeld[], int suche, int m, int r, int l){
		if(zahlenfeld[m] == suche) {
			System.out.println("an der Stelle " + m + " steht die Zahl " + suche);
		}
		if(zahlenfeld[m]> suche){
			r = m - 1;
			m = (l + r)/2;
			suche(zahlenfeld, suche, m, r, l);
		}
		else if(zahlenfeld[m] < suche){
			l = m + 1;
			m = (l + r)/2;
			suche(zahlenfeld, suche, m, r, l);
		}
		
	}
}

Meine Frage: Wie kann ich die rekursive Methode Suche nun so erweitern, dass sie auch die weiteren Stellen des Arrays, die mit meiner Variablen suche identisch sind, ausgibt?

Hatte überlegt in die If-Bedingung zahlenfeld[m] == suche zwei weitere Bedingung einzubauen, wenn m ungleich 0 bzw. ungleich zahlenfeld.length ist müsste er die Methode erneut aufrufen (weil er ja noch nicht bis zum Ende gesucht hat und weitere Zahlen im sortierten Feld existieren könnten). Bin aber wie gesagt nicht auf die Abbruch-Bedingung gekommen und habe zu weit gesucht!
 
Zuletzt bearbeitet:
G

Gucky

Top Contributor
Das Zahlenfeld ist doch sortiert. Von welcher Seite aus suchst du denn?
Wenn du von "unten" suchst, so könntest du die Methode so definieren:
Java:
public ArrayList<Integer> such(int[] array, int index, ArrayList<Integer> funde){
 if (m == zahlenfeld.length) gib funde zurück;
 if (zahlenfeld[index] == suchZahl){
  füge index funde hinzu;
  inkrementiere index;
  gib suche(array, index, funde) zurück;
 if (zahlenfeld[index] > suchZahl) gib funde zurück;
 inkrementiere index;
 gib suche(array, index, funde) zurück;
}
 
M

marvpaul

Mitglied
Ich will die Suche ja optimieren und führe deswegen den Mittelwert und die rechte und linke Grenze des Arrays. Die verändern sich je nach dem wie groß die gesuchte Variable ist. Und ich bekomm es nicht hin das er nach dem ersten gefundenen Wert weiter suchen soll. Dein vorgeschlagener Pseudocode funktioniert nur für bestimmte Zahlen (z.B. nicht für 3) und wirft ein out of bounds (lag vllt. auch an meiner Umsetzung).
 
Flown

Flown

Administrator
Mitarbeiter
So ich liefere dir jetzt man eine normal rekursive Methode zum Suchen von Indizes (hierfür keine Ordnung nötig!) und dann noch deine Wunschimplementierung. Ich möchte mich nochmals in Prosa dazu äußern, denn viele Menschen finden es schwer eine Rekursion zu bauen.
  1. (Optional) Eine simple Schnittstelle bieten (bei mir: binarySearchIndices(int[], int)
  2. Parameter für die Rekursion zusammenstellen
    • Das Array mit den Daten selbst
    • Die gesuchte Nummber
    • Ein Indizes-Array
    • Aktuell gefundene Objekte (später für die Längenbestimmung des Indizes Array nötig)
    • Start des Suchbereichs
    • Ende des Suchbereichs
  3. Abbruchbedingungen schaffen
    • Wenn Start und Ende gleich sind (d.h. Array leer) -> gib die Funde zurück
    • Wenn Start und Ende ein Element eingrenzen -> Prüfen ob die Zahl die Gesuchte ist, wenn ja: in das Indizesarray eintragen und Fundanzahl erhöhen
  4. Rekursion bilden
    • Pivotelement ermitteln (Mitte zwischen Start und Ende)
    • Wenn gesuchte Zahl kleiner dem Element an der Pivotstelle, dann die Methode nochmals mit dem neuen Bereich Start bis Pivotelement starten
    • Wenn gesuchte Zahl größer dem Element an der Pivotstelle, dann die Methode nochmals mit dem neuen Bereich Pivotelement bis Ende starten
    • Wenn die gesuchte Zahl an der Pivotstelle steht, erst Methode mit Start bis Pivot aufrufen und danach Pivot bis Ende

Und hier der Code:

Java:
public class Search {
  
  public static void main(String... args) {
    int[] array = { 5, 3, 6, 8, 1, 8, 8, 7, 5, 3, 0, 1 };
    Arrays.sort(array);
    System.out.println(Arrays.toString(array));
    long start = System.nanoTime();
    int[] indices = searchIndices(array, 1);
    long duration = System.nanoTime() - start;
    System.out.println("linear search took: " + duration);
    System.out.println(Arrays.toString(indices));
    start = System.nanoTime();
    int[] indices2 = binarySearchIndices(array, 1);
    duration = System.nanoTime() - start;
    System.out.println("binsearch took: " + duration);
    System.out.println(Arrays.toString(indices2));
  }
  
  public static int[] binarySearchIndices(int[] array, int number) {
    int[] indices = new int[array.length];
    int found = binarySearchIndices(array, number, indices, 0, 0, array.length);
    return Arrays.copyOfRange(indices, 0, found);
  }
  
  private static int binarySearchIndices(int[] array, int number, int[] indices, int found, int start, int end) {
    // case: empty - array : []
    if (end - start <= 0) {
      return found;
    }
    // case: one element - array [element]
    else if (end - start <= 1) {
      if (array[start] == number) {
        indices[found++] = start;
      }
      return found;
    }
    // case: range - array [element, ...]
    else {
      // pivot element
      int m = (start + end) / 2;
      // number must be on the left side of array
      if (array[m] > number) {
        return binarySearchIndices(array, number, indices, found, start, m);
      }
      // number must be on the right side of array
      else if (array[m] < number) {
        return binarySearchIndices(array, number, indices, found, m, end);
      }
      // number is hit but more could be on the left and/or right side
      else {
        int f = binarySearchIndices(array, number, indices, found, start, m);
        return binarySearchIndices(array, number, indices, f, m, end);
      }
    }
  }
  
  public static int[] searchIndices(int[] array, int number) {
    int[] indices = new int[array.length];
    int found = searchIndices(array, number, indices, 0, 0, array.length);
    return Arrays.copyOfRange(indices, 0, found);
  }
  
  private static int searchIndices(int[] array, int number, int[] indices, int found, int cur, int length) {
    if (cur == length) {
      return found;
    }
    if (array[cur] == number) {
      indices[found++] = cur;
    }
    return searchIndices(array, number, indices, found, cur + 1, length);
  }
}
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Methoden Binäre Suche als rekursive Variante Java Basics - Anfänger-Themen 5
kulturfenster rekursive Binaere Suche Java Basics - Anfänger-Themen 12
M Rekursive Java-Methode Java Basics - Anfänger-Themen 13
G Rekursive Methode liefert augenscheinlich keinen boolean-Wert zurück. Java Basics - Anfänger-Themen 4
veryck Methoden Rekursive Methoden mit Rückgabeparameter Java Basics - Anfänger-Themen 9
macle Rekursive String Methode, Gerade Zahlen rausfiltern Java Basics - Anfänger-Themen 10
M Rekursive Prüfung ob ein Array sortiert ist... Java Basics - Anfänger-Themen 4
J Rekursive swapArray Methode Java Basics - Anfänger-Themen 69
D Rekursive Methode Java Basics - Anfänger-Themen 8
R Methoden rekursive Methoden Java Basics - Anfänger-Themen 6
O Quersumme rekursive Methode Java Basics - Anfänger-Themen 3
B Treetable (rekursive Funktion) aufbauen von Datenbank Java Basics - Anfänger-Themen 4
M Rekursive Methode Programmieren Java Basics - Anfänger-Themen 3
J rekursive Methode Java Basics - Anfänger-Themen 26
M rekursive division/0 mit exception Java Basics - Anfänger-Themen 18
J Rekursive Methode - Ziffern einer Zahl ausgeben Java Basics - Anfänger-Themen 2
M Rekursive Dateiliste erstellen mit Dateiendung(en) ?? Java Basics - Anfänger-Themen 4
S Rekursive Methode Java Basics - Anfänger-Themen 8
O Rekursive Methode Java Basics - Anfänger-Themen 4
V Methoden Rekursive Methode mit String als Rückgabe Java Basics - Anfänger-Themen 7
K Rekursive Methode Java Basics - Anfänger-Themen 1
K Rekursive Methode für Fakultät mit BigInteger Java Basics - Anfänger-Themen 10
L Rekursive Methode a * b berechnen Java Basics - Anfänger-Themen 2
L Rekursive Methode zur Berechnung der Potenz q hoch p Java Basics - Anfänger-Themen 17
J Methoden Rekursive Return Methode Java Basics - Anfänger-Themen 2
G Harmonische Rekursive Folge Java Basics - Anfänger-Themen 3
T Stack Overflow - Rekursive Fibonacci Java Basics - Anfänger-Themen 10
B Datentypen Suchbaum - Rekursive Ausgabe Java Basics - Anfänger-Themen 1
P Methoden Rekursive Methode für Potenzen Java Basics - Anfänger-Themen 2
B Rekursive Algorithmus schreiben Java Basics - Anfänger-Themen 8
S Eine rekursive Lösung Java Basics - Anfänger-Themen 4
S Int zu Hexadezimal - Rekursive Methode Java Basics - Anfänger-Themen 2
N Rekursive Addition mit Scanner Java Basics - Anfänger-Themen 12
shiroX OOP Rekursive und Iterative Definition Java Basics - Anfänger-Themen 2
B Methoden Rekursive Methoden Java Basics - Anfänger-Themen 2
T Iterative Pi Berechnung in Rekursive Java Basics - Anfänger-Themen 2
C rekursive methode Java Basics - Anfänger-Themen 2
D Methoden Rekursive Methoden Java Basics - Anfänger-Themen 13
R rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
M Stürzen alle Rekursive Methoden irgendwann ab? Java Basics - Anfänger-Themen 11
D Primzahlen und Rekursive Liste Java Basics - Anfänger-Themen 29
R Rekursive Methode, Files finden Java Basics - Anfänger-Themen 2
S rekursive folge verbessern Java Basics - Anfänger-Themen 2
C rekursive Methode verstehe nicht! Java Basics - Anfänger-Themen 3
S Methoden rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
E Rekursive Methode Java Basics - Anfänger-Themen 3
N Methoden Rekursive Fibonaccizahlen mit Array Java Basics - Anfänger-Themen 2
R Rekursive Ausgabe eines Binärbaums Java Basics - Anfänger-Themen 4
J Methoden Rekursive Potenz ohne Math.Pow() Java Basics - Anfänger-Themen 9
A Rekursive Methode in Iterative umwandeln Java Basics - Anfänger-Themen 6
S Labyrith Rekursive Wegsuche Java Basics - Anfänger-Themen 4
C Rekursive Methode - Ziffern in Zahl Java Basics - Anfänger-Themen 33
U Dezimal zu Hexadezimal rekursive Funktion Java Basics - Anfänger-Themen 8
M rekursive Funktion zur Berechnung der Spiegelzahl Java Basics - Anfänger-Themen 7
L iterative und rekursive Folge Java Basics - Anfänger-Themen 20
G Rekursive Methode Java Basics - Anfänger-Themen 3
A rekursive Listen in Java? Java Basics - Anfänger-Themen 5
B OOP Einfach verkettete Liste - rekursive Methoden Java Basics - Anfänger-Themen 1
E Rekursive Methode mit Zufallsarray Java Basics - Anfänger-Themen 6
E Rekursive Methode Java Basics - Anfänger-Themen 18
U Rekursive lösung von pascal dreieck Java Basics - Anfänger-Themen 11
M Rekursive Methode - wo ist der Fehler? Java Basics - Anfänger-Themen 4
J rekursive methode Java Basics - Anfänger-Themen 6
H ScrollBar inaktiv / Rekursive Methode Java Basics - Anfänger-Themen 4
J Rekursive Methode Java Basics - Anfänger-Themen 11
G Rekursive Methode Java Basics - Anfänger-Themen 5
N Rekursive Berechnung der Höhe eines binären Baumes Java Basics - Anfänger-Themen 4
K Rekursive Methoden Java Basics - Anfänger-Themen 15
K Rekursive Funktion (Verständnissfrage) Java Basics - Anfänger-Themen 5
S Rekursive Bruch potenzierung Java Basics - Anfänger-Themen 2
D rekursive Summenberechnung Java Basics - Anfänger-Themen 8
J Rekursive Methode: Fakultaet berechnen Java Basics - Anfänger-Themen 5
E Rekursive definierten Folge Java Basics - Anfänger-Themen 10
A HILFE! Rekursive Funktion Java Basics - Anfänger-Themen 20
F Rekursive Aufrufe, Parameterübergabe, call by reference Java Basics - Anfänger-Themen 3
G Rekursive Berechnung von n über k schlägt fehl Java Basics - Anfänger-Themen 5
B Rekursive & schreiben im ArrayList Java Basics - Anfänger-Themen 2
J Rekursive Fkt. Java Basics - Anfänger-Themen 2
A Rekursive Dateisuche Java Basics - Anfänger-Themen 12
K rekursive Funktion mit mehreren Parametern Java Basics - Anfänger-Themen 5
G rekursive Methode Java Basics - Anfänger-Themen 3
N rekursive Beispiele Java Basics - Anfänger-Themen 3
G rekursive u iterative Methode Java Basics - Anfänger-Themen 8
G Rekursive Methode Java Basics - Anfänger-Themen 7
ven000m Rekursive Funktionen - Frage Java Basics - Anfänger-Themen 16
D rekursive ausgabe einer zahl Java Basics - Anfänger-Themen 14
S Rekursive Funktionen in imperative Funktionen umwandeln Java Basics - Anfänger-Themen 2
M Rekursive Binärsuche Java Basics - Anfänger-Themen 6
S rekursive methoden Java Basics - Anfänger-Themen 5
Y Suche von Studenten anhand Ihrer Eigenschaften. Java Basics - Anfänger-Themen 1
F Auf der Suche in π Java Basics - Anfänger-Themen 13
C Suche Nachhilfe in Java Java Basics - Anfänger-Themen 5
T Binärbaum-Suche Implementation Java Basics - Anfänger-Themen 6
A suche dringend Hilfe!! Java Basics - Anfänger-Themen 6
N Operatoren Schreibtischtest der Reihen-Suche nach Aufschluss in die Basics Java Basics - Anfänger-Themen 1
B Suche free SVN Hosting Java Basics - Anfänger-Themen 12
S Binäre-Suche Algorithmus Java Basics - Anfänger-Themen 1
S Java Lineare-Suche Zeitmessung Java Basics - Anfänger-Themen 5
S Java Lineare Suche Java Basics - Anfänger-Themen 1
S Binäre-Suche bei unsortierten Daten Java Basics - Anfänger-Themen 7

Ähnliche Java Themen

Anzeige

Neue Themen


Oben