Array rekursiv untersuchen

B

babuschka

Top Contributor
Hallo, ich schon wieder. :D

Es geht um Folgendes:

Man hat ein Array bel. Länge, das zufällige Zahlen enthält, die aufsteigend sortiert sind.

Man will wissen, ob eine bestimmte Zahl in dem Array steht und wenn ja, an welcher Stelle.

Ist das Element nicht enthalten, will man die Stelle, an der das Element gestanden hätte negieren und davon 1 abziehen.


Beispiel: [0,2,3,4]

Sucht man 3, soll die Methode, die man implementieren soll, 2 zurückgeben.

Sucht man nach 7, so -5 (=4*(-1)-1).


Das soll man rekursiv implementeiren und ich suche erstmal nur nach einer Idee, wie man es rekursiv sich denken kann.


Ich habe mir irgendwie sowas gedacht:


Trivialfälle sind:

leeres Array: return -1

Array mit einem Element. Wenn Element mit dem Eintrag übereinstimmt, gebe die Stelle des Arrayelements zurück. Wenn das Element, das man suchen will, kleiner ist, gebe -i zurück, wenn das Element das i-te Element ist.


Wenn das zu suchende Element größer als das eine vorhandene Array-Element ist, gebe -(i+2) zurück, wenn das vorhandene Array Element an i-ter Stelle steht.


Aber irgendwie komme ich nun nicht weiter.


Wenn ich zum Beispiel das Array [8,9,10,15] habe:

Wie kann man das aufsplitten?

In [8] und [9,10,15] und dann wiederum in [9] und [10,15] usw.?


Aber wie zählt man dann das jeweils zusammen:

Wenn ich zum Beispiel nach 13 suche:


Zuerst bei [8]: Da hätte ich (8 steht an 0-ter Stelle): -2

Dann bei [9,10,15]: Da hätte ich (wenn 9 wieder die 0-te Stelle sein soll): -3

Dann bei [10,15]: Da hätte ich (ist 10 wieder die 0-te Stelle?) -2

Und dann noch bei [15]: Da hätte ich (wenn 15 die 0-te Stelle ist) -1




Aber es muss ja -4 herauskommen. :bahnhof:
 
B

babuschka

Top Contributor
Ich habe mir mal meine Gedanken gemacht und habe mir Folgendes überlegt:

Java:
public int searchInArray(int[] array, int j){

if( array.length() == 0) return -1;
if( array.length() == 1){
      if( j== array[0]) return 0;
      if( j< array[0]) return -1;
      if( j> array[0]) return -2;
  }

for( int i=0; i< array.length(); i++){
  if( j<array[i]) {
    int[] array1=new int[1];
    return -i + searchInArray(array1, j);
  }

}


Vielleicht kann mir ja jemand ein Feedback geben?


LG Dennis
 
Final_Striker

Final_Striker

Top Contributor
Die for-Schleife brauchst du nicht, soll je rekursiv und nicht iterativ sein.

Du musst doch quasi nur über das Array laufen und schauen ob das aktuelle Element kleiner oder gleich dem gesuchten Element ist. Ist das nicht der Fall, kannst du die Suche abbrechen und das aktuelle Element dann negieren usw.
 
B

babuschka

Top Contributor
Ist gar nichts von minm Ansatz brauchbar?

Wi lauf ich denn ohn jede Schleife durch das Array?
 
Final_Striker

Final_Striker

Top Contributor
Wi lauf ich denn ohn jede Schleife durch das Array?

z.B. so:

Java:
	static int[] arr = new int[] { 1, 3, 5, 7 };

	static void rekursiveSearch(int[] arr, int index) {

		if (index < arr.length) {
			System.out.println(arr[index]);
			rekursiveSearch(arr, index+1);
		}
	}

	public static void main(String[] args) {
		rekursiveSearch(arr, 0);
	}
 
S

Spacerat

Gast
Also zunächst erstmal sollte man das Array keinesfalls stückeln (würde evtl. zu viele [c]new int[x][/c] bedeuten und gc überlasten). Ich könnte das nur mit 2 Methoden lösen, solange die Arrays sortiert vorliegen, per [c]binärSuche[/c].
Java:
public int arraySearch(int[] hay, int needle) {
  return arraySearch(hay, needle, 0, hay.length);
}

public int arraySearch(int[] hay, int needle, int fromIndex, int toIndex) {
  int low = fromIndex;
  int high = toIndex - 1;
  int mid = (low + high) / 2;
  // ... uhhh je... schon muss ich wieder überlegen, wie es weiter ging... dauert länger... ;)
  // irgend was mit return arraySearch(hay, needle, mid, high + 1);
  // bzw. return arraySearch(hay, needle, low, mid);

  // ok... erst mal ohne Garantie... aber so etwa in der Richtung...
  if(mid > 0 && mid < hay.length) {
    int midVal = hay[mid];
    if (midVal < key) {
      return arraySearch(hay, needle, low, mid);
    } else if (midVal > key) {
      return arraySearch(hay, needle, mid, high + 1);
    } else {
      return mid;
    }
  }
  return -(high + 1);
}
 
Zuletzt bearbeitet von einem Moderator:
B

babuschka

Top Contributor
Mein Problem bei der Idee mit der Binärsuche:

Ich habe zum Beispiel das Array

[0, 1, 2 , 3, 4]

Gesucht werden soll ob 7 vorkommt.

Was ist die Mitte? Der Wert 2?

7 ist größer als 2 als müsste ich die zweite Hälfte durchsuchen.

Das ist [3, 4]?

Was ist da die Mitte? Und wie komme ich denn auf die Ausgabe -6, die vorgesehen ist?


Das Prinzip ist mir klar geworden, aber an diesen Feinheiten hapert es noch gewaltig.
 
B

babuschka

Top Contributor
Stark an dem Wiki-Artikel orientiert, habe ich nun Folgendes:

Java:
public int searchInArray(int indexStart, int indexEnd, int searchedNumber, int[] array){

if( indexStart > indexEnd){
   if( searchedNumber < array[indexStart] ) return (indexEnd + 1) * (-1) -1;
   
   if( searchedNumber > array[indexStart] ) return (indexStart +1) * (-1) -1;
}

int indexMiddle = indexStart + ( (indexEnd - indexStart) / 2 );

if( searchedNumber < array[indexMiddle] ){
     return searchInArray( indexStart, indexMiddle - 1, searchedNumber, array);
  }

if( searchedNumber > array[indexMiddle] ){
     return searchInArray( indexMiddle + 1, indexEnd, searchedNumber, array );
  }

return indexMiddle;

}


Ich habe mir das an zwei, drei Beispielen mal angesehen und m.E. haut es hin.
Am PC habe ich's allerdings noch nicht getestet, sondern nur händisch.


LG Dennis

[Ein Feedback ist wie immer willkommen. ;)]
 
L

langhaar!

Bekanntes Mitglied
So blöd, daß keiner antwortet? ???:L

So blöd, daß du keine Frage gestellt hast.

Du hast dir Code angesehen und bist der Meinung, der sollte funktionieren. Ok.
Und was erwartest du jetzt vom Forum? :autsch:

Ohne konkrete Frage wird sich wohl kaum einer in das Thema vertiefen und dir eine Abhandlung schreiben, die dich evtl. gar nicht interessiert.
 
S

Spacerat

Gast
@TO: Weis gar nicht was du hast. Deine Methode ist doch 1:0,7 von Wikipedia übernommen (vllt. hätte ich mir diesen Link auch mal ansehen sollen. :oops:)... Wenn sie nicht funktioniert, weisst du hoffentlich, an welchem Teil du noch was ändern darfst. ;)
 
B

babuschka

Top Contributor
Im Großen und Ganzen funktioniert es.

Ich habe aber ein Problem, das ich nicht beheben kann:

Suche ich zum Beispiel in dem Array

[1,3,7,20,21]

nach dem Element 22, so kommt die Fehlermeldung, die ich unten als Screenshot angehängt habe.
Weiß jemand Rat?




Dies der Code:

Java:
public class ArraySearch{


public int searchInArray(int indexStart, int indexEnd, int searchedNumber, int[] array){
 
if( indexStart > indexEnd){
   if( searchedNumber < array[indexStart] ) return (indexEnd + 1) * (-1) -1;
   
   if( searchedNumber > array[indexStart] ) return (indexStart +1) * (-1) -1;
}
 
int indexMiddle = indexStart + ( (indexEnd - indexStart) / 2 );
 
if( searchedNumber < array[indexMiddle] ){
     return searchInArray( indexStart, indexMiddle - 1, searchedNumber, array);
  }
 
if( searchedNumber > array[indexMiddle] ){
     return searchInArray( indexMiddle + 1, indexEnd, searchedNumber, array );
  }
 
return indexMiddle;
 
}

public static void main( String[] args){
	int[] testArray = new int[5];
	
	testArray[0] = 1;
	testArray[1] = 3;
	testArray[2] = 7;
	testArray[3] = 20;
	testArray[4] = 21;
	
	ArraySearch b = new ArraySearch();
	
	System.out.println(b.searchInArray(0, 4, 22, testArray));
	
}


}
 
F

Firephoenix

Gast
Und wo ist das jetzt das Problem?
Irgendwann ist dein Mittlerer Index das letzte Element, da du die suche darauf eingrenzt, dort findest du die Zahl aber nicht, also erhöhst du den index nochmal und rufst die Methode auf, beim nächsten durchlauf greifst du auf ein Element hinter dem Array zu und es knallt.

Dein Programm macht also genau das was du im Moment implementiert hast.

Falls du weißt wie du den Fall behandeln willst, wenn die gesuchte Zahl garnicht im Array vorhanden ist, dann solltest du dir die passende Stelle im Code suchen und passend abändern :)

Gruß
 
B

babuschka

Top Contributor
Also ich lande irgendwann bei

indexMiddle = 4

Dann habe ich testArray[4] = 21 < 22

und würde dann den Startindex auf 5 setzen und da knallt es dann vermutlich.

Aber wie ich das beheben kann, ist mir momentan nicht klar, zumal die Suche funktioniert, wenn ich zum Beispiel nach -5 Suche, da kommt dann wie gewünscht -1 heraus.
 
S

Spacerat

Gast
Was bitte genau heisst denn hier "vermutlich"? Es müsste "ganz sicher" heissen. Natürlich knallts dort, weil eben in jener Zeile 7 mit eben jenem zu grossen Index auf das Array zugegriffen wird. Ergo verwendet man in den Zeilen 7 und 9 stattdessen "indexEnde", welcher noch im grünen Bereich liegen sollte oder lässt sich für meine Version was passendes in Zeile 24 einfallen (obwohl... der kann nicht funktionieren, weil dort in den Zeilen 16 und 18 "key" statt "needle" verwendet wird :oops:).
[EDIT]Man war des spät Gestern...
Java:
public class ArraySearch {

	public int arraySearch(int[] hay, int needle) {
		return arraySearch(hay, needle, 0, hay.length);
	}

	public int arraySearch(int[] hay, int needle, int fromIndex, int toIndex) {
		int low = fromIndex;
		int high = toIndex - 1;
		int mid = (low + high) / 2;
		if(low != high && mid >= 0 && mid < hay.length) {
			int midVal = hay[mid];
			if (midVal > needle) {
				return arraySearch(hay, needle, low, mid + 1);
			} else if (midVal < needle) {
				return arraySearch(hay, needle, mid + 1, high + 1);
			} else {
				return mid;
			}
		}
		return -(high + 1) // bzw. -toIndex;
	}
 
	public static void main( String[] args) {
		int[] testArray = {1,3,7,20,21};

		ArraySearch b = new ArraySearch();
		System.out.println(b.arraySearch(testArray, 22));
	}
}
nimmsu so... ;)[/EDIT]
 
Zuletzt bearbeitet von einem Moderator:
B

babuschka

Top Contributor
In Zeile 9 habe ich jetzt

if( searchedNumber > array[indexEnd] ) return (indexEnd +1) * (-1) -1;

In Zeile 7 bin ich mir nicht sicher, was ich da nehmen muss.

???:L
 
S

Spacerat

Gast
Hmmm... wie soll ich sagen... der Startindex überholt den Endindex. Wenn dieser Fall eintritt genügt es, einfach den Endindex negiert zurückzugeben, denn er ist definitiv stets im Bereich der Arrayelemente ([c]0 <= Endindex <= Arraylänge[/c]). Deswegen kannst du dir eine zweite if-Abfrage auch sparen.

So gross, selbst wenn es so aussieht, sind die Unterschiede in unseren Methoden übrigens nicht. Ich spare mir lediglich einen Methodenaufruf, indem ich prüfe ob high und low gleich sind, während du erst in der nächsten Rekursion prüfst, ob low grösser als high ist. Entscheidend aber ist, dass wenn dieser Fall eintritt, der Endindex negiert zurückgegeben werden kann.
 
B

babuschka

Top Contributor
Ich habe heute wohl meinen besonders schwerfälligen Tag.

Leider habe ich noch nicht verstanden, wie Zeile 7 verbessert werden müsste.


Könntest Du es nochmal erklären, wenn das überhaupt noch möglich ist?
 
S

Spacerat

Gast
Könntest Du es nochmal erklären, wenn das überhaupt noch möglich ist?
Aber klar... geht ja schnell... WEGRATIONALISIEREN... AUSLÖSCHEN... TÖÖÖÖÖTEN... ;)
Oder besser:
[JAVA=3] if(indexStart > indexEnd) {
return -(indexStart+1) // bzw. -(indexEnd+2);
}
// das entspricht dann so aber nicht mehr
// der eigentlichen Aufgabenstellung...
// es müsste nämlich -(indexEnd+1)
// zurückgegeben werden, isch denk'.
// naja, mit der Addition kann man ja Experimentieren.[/code]
 
Zuletzt bearbeitet von einem Moderator:
B

babuschka

Top Contributor
Okay, damit funktionieren alle Fälle, danke.

Aber inwiefern entspricht das nicht der Aufgabenstellung? ???:L

Es kommt doch das Gewünschte jeweils heraus.
 
S

Spacerat

Gast
du bekommst jetzt den negierten EndIndex -2 (statt -1).
[EDIT]Ach ja... machst du noch 'n "Erledigt" an den Thread, büdde?[/EDIT]
 
Zuletzt bearbeitet von einem Moderator:
Ähnliche Java Themen
  Titel Forum Antworten Datum
O Enum Array Rekursiv abarbeiten Java Basics - Anfänger-Themen 44
B Fakultätsfunktion Rekursiv Berechnen aber mit Array Java Basics - Anfänger-Themen 10
B Fibonacci Zahlen rekursiv Array Java Basics - Anfänger-Themen 12
G Rekursiv Array Elemente quadrieren Java Basics - Anfänger-Themen 2
G Array rekursiv teilen und aufsummieren Java Basics - Anfänger-Themen 9
U Muster in einem Array erkennen Java Basics - Anfänger-Themen 8
L Array mit Wörtern gestalten Java Basics - Anfänger-Themen 2
Gaudimagspam Nummern generieren Array Java Basics - Anfänger-Themen 4
Eule25 Methode mit Array Java Basics - Anfänger-Themen 4
J Methoden Frage: Array-Werte in anderer Methode ändern Java Basics - Anfänger-Themen 4
FelixN Array mit verschiedene Datentypen als Rückgabewert? (Long und Double) Java Basics - Anfänger-Themen 3
P Nutzer entscheiden lassen, wie viele Zahlen dieser in ein Array eingeben möchte. Java Basics - Anfänger-Themen 6
J Array; Elemente kopieren Java Basics - Anfänger-Themen 17
JD_1998 Array-Position aus einer Methode in einer anderen ausgeben (Kurze Frage) Java Basics - Anfänger-Themen 2
JD_1998 Random Array sortieren mit Hilfe einer Methode Java Basics - Anfänger-Themen 4
M Objekte in Array speichern und ausgeben Java Basics - Anfänger-Themen 17
C Array-Werte werden gemischt, ohne Logik Java Basics - Anfänger-Themen 2
A eine neue normale String-Array von einer String-Array, die in for schleife ist, schaffen Java Basics - Anfänger-Themen 3
A keine Ergebnisse - String nummer in array nummer converting Java Basics - Anfänger-Themen 1
Z Char Array an zufälligen stellen mit einem "x" füllen. Java Basics - Anfänger-Themen 4
P JSON-Array auf Excel-Spalten verteilen? Java Basics - Anfänger-Themen 5
V Array aus Klasse um vererbte Elemente erweitern Java Basics - Anfänger-Themen 3
J Array über Getter erlangen Java Basics - Anfänger-Themen 34
K Übergabe von Werten (zweidimensionales Array) aus einer Methode an zweidimensionales Array in main() Java Basics - Anfänger-Themen 3
T Array füllen Java Basics - Anfänger-Themen 11
P Was genau bringt mir es ein Array in eine Liste zu bringen Java Basics - Anfänger-Themen 3
S Auf Array aus Objekten zugreifen? Java Basics - Anfänger-Themen 1
G Variablen Array Länge über den Konstruktor definieren Java Basics - Anfänger-Themen 4
A Speicherbereich von Array nicht zusammenhängend? Java Basics - Anfänger-Themen 8
S Java Array Probleme Java Basics - Anfänger-Themen 3
S Java Array Problem... Java Basics - Anfänger-Themen 2
C 2dimensionales array, Lagerverwaltung Java Basics - Anfänger-Themen 64
P Verschachtelte Array Liste Java Basics - Anfänger-Themen 2
P Performance Array und Liste Java Basics - Anfänger-Themen 13
M Array Summe bestimmen? Java Basics - Anfänger-Themen 14
parrot Array Übung Java Basics - Anfänger-Themen 25
parrot Array: Methode fügeHinzu Java Basics - Anfänger-Themen 13
parrot Array Java Basics - Anfänger-Themen 4
L 2 Dimensional Array werte überschreiben Java Basics - Anfänger-Themen 1
A char array wird überschrieben Java Basics - Anfänger-Themen 6
L Zufälliges 2d array befüllen Java Basics - Anfänger-Themen 27
L x und y Koordinaten in ein Array schreiben Java Basics - Anfänger-Themen 7
U Dreiecks-Matrix mit Array Java Basics - Anfänger-Themen 3
I Java zweidimensionales array befüllen mit for-schleife Java Basics - Anfänger-Themen 2
P Enums in Array abspeichern Java Basics - Anfänger-Themen 4
J Array Speicherplatz berechnen Java Basics - Anfänger-Themen 35
L Iterieren durch eine ArrayList. Integer Array wird übergeben Java Basics - Anfänger-Themen 17
Z Matrix Klasse mit Mehrdimensionalen Array (Addition, Multiplikation, to String) Java Basics - Anfänger-Themen 57
Z Methoden Array horizontal spiegeln Java Basics - Anfänger-Themen 19
K Array alle Werte aufsummieren und ausgeben Java Basics - Anfänger-Themen 6
J zweidimensionales Array Java Basics - Anfänger-Themen 1
A Array Elemente extrahieren ! Java Basics - Anfänger-Themen 4
M Quiz in Java programmieren mit Array Java Basics - Anfänger-Themen 8
A Array aufaddieren ! Java Basics - Anfänger-Themen 5
F Auto String mit Array Name aus Datei... oder so ähnlich Java Basics - Anfänger-Themen 4
H Ein gegebenes Int Array zu Zwei Arrays zurück geben Java Basics - Anfänger-Themen 6
J Elemente in einem 2D-Array summieren Java Basics - Anfänger-Themen 6
J String aus einem Array entfernen Java Basics - Anfänger-Themen 10
J Array differenzieren Java Basics - Anfänger-Themen 2
M Rekursive Prüfung ob ein Array sortiert ist... Java Basics - Anfänger-Themen 4
J Methoden set Methode array Java Basics - Anfänger-Themen 2
I Array übernimmt immer den letzten Input. Java Basics - Anfänger-Themen 14
E 2D Array - char durch die Matrix "wandern" lassen Java Basics - Anfänger-Themen 7
Kirby_Sike Anzahl vorkommender Elemente im Array zählen Java Basics - Anfänger-Themen 9
A Array problem Java Basics - Anfänger-Themen 16
NeoLexx Variable für Array wird nicht korrekt übergeben Java Basics - Anfänger-Themen 45
F Integerzahl als Array halten Java Basics - Anfänger-Themen 4
1 Array nimmt falschen Wert auf! Java Basics - Anfänger-Themen 2
J Neue Werte in ein Array hinzugeben Java Basics - Anfänger-Themen 8
I Array funktioniert nicht. Java Basics - Anfänger-Themen 2
J String Array zu Map<Character, List<Character>> mit Streams Java Basics - Anfänger-Themen 1
L Wie frage ich ab, ob in einem Array, Werte doppelt vorkommen? Java Basics - Anfänger-Themen 4
C 2-Dimensionales Array in Eindimensionales Array Java Basics - Anfänger-Themen 1
H Frage zum 2d Array Java Basics - Anfänger-Themen 1
L Array sortieren Java Basics - Anfänger-Themen 4
Kirby_Sike Fehlende Int Werte aus Array mit streams finden Java Basics - Anfänger-Themen 19
Ellachen55 Wie nach häufigste Werte im Array suchen? Java Basics - Anfänger-Themen 2
V Array auf eine Zahl durchsuchen Java Basics - Anfänger-Themen 15
M Bubblesort ohne Array Java Basics - Anfänger-Themen 30
B Array Redundanz Java Basics - Anfänger-Themen 1
Kirby_Sike Array Replacing Java Basics - Anfänger-Themen 3
J Array vertauschen ohne ein neues anzulegen?! Java Basics - Anfänger-Themen 10
P Arraylist zu einem Array bringen mit Verschachtelung Java Basics - Anfänger-Themen 11
S Nutzereingabe splitten und in string array wieder ausgeben. Java Basics - Anfänger-Themen 1
L Java Int-Array, Zahlen sortieren Java Basics - Anfänger-Themen 8
M Auf einen Array innerhalb eines Objekts zugreifen Java Basics - Anfänger-Themen 5
H Array-Sortierer Java Basics - Anfänger-Themen 1
F Array Java Basics - Anfänger-Themen 3
Kirby_Sike ArrayOutOfBoundsException bei boolean Array Java Basics - Anfänger-Themen 19
F Zwei Dimensionles Array Java Basics - Anfänger-Themen 21
Kirby_Sike Multidimensionales Array zuschneiden Java Basics - Anfänger-Themen 23
M Ist es möglich, das größte und zweitgrößte element in einem Array mit nur einer Schleife ausfindig zu machen ? Java Basics - Anfänger-Themen 19
B Von Array nur eine bestimmte Anzahl bekommen Java Basics - Anfänger-Themen 3
D NullPointerException im Array Java Basics - Anfänger-Themen 4
S 2D Array Matrizen Java Basics - Anfänger-Themen 7
W OOP Warenlager mit Array(Konstruktor, Methoden) Java Basics - Anfänger-Themen 39
I Methoden char Array Aufgabe (bitte hierbei um Hilfe) Java Basics - Anfänger-Themen 3
A Array richtig füllen Java Basics - Anfänger-Themen 2
H Array Slot frei machen Java Basics - Anfänger-Themen 3
H Array Slot frei machen Java Basics - Anfänger-Themen 4

Ähnliche Java Themen

Anzeige

Neue Themen


Oben