Array rekursiv untersuchen

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:
 

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

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.
 

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:

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.
 

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. ;)]
 

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. ;)
 

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ß
 

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:

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.
 

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:

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
1 Array rekursiv durchlaufen Java Basics - Anfänger-Themen 8
R0m1lly Kombinationen aus int array rekursiv Java Basics - Anfänger-Themen 2
B Array nach Wert prüfen rekursiv Java Basics - Anfänger-Themen 5
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
T Array verkleinern Java Basics - Anfänger-Themen 2
J Array aus Numberfield Eingaben Java Basics - Anfänger-Themen 7
D Array List mit Objekten sortieren Java Basics - Anfänger-Themen 2
onlyxlia Anzahl Random Zahlen mit Scanner abfragen und in Array speichern Java Basics - Anfänger-Themen 10
Ü Java Array - Buchstaben als Zahlen ausgeben Java Basics - Anfänger-Themen 22
Ü Zweidimensionales Array in der ersten Zeile deklarieren Java Basics - Anfänger-Themen 13
Thomas Uppe 2D Array Reihenfolge vermischen Java Basics - Anfänger-Themen 4
T array auslesen Java Basics - Anfänger-Themen 2
Nitrogames Variablen Variable aus JOptionPane Abfrage in Array einfügen Java Basics - Anfänger-Themen 4
moini Auf Array aus Superklasse zugreifen? Java Basics - Anfänger-Themen 2
J ArrayList in 2D-Array konvertieren. Java Basics - Anfänger-Themen 48
M NullPointerException: Cannot read the array length because "this.Kinder" is null Java Basics - Anfänger-Themen 1
P Wieso kann ich als Index für einen Array einen Char angeben? Java Basics - Anfänger-Themen 3
Finn_lol Fehlermeldung bei Schleife mit Array Java Basics - Anfänger-Themen 4
Proxy Chars vor array übergabe toLowerUpcase Java Basics - Anfänger-Themen 14
iAmFaiinez Primzahlen Tester ohne Array Java Basics - Anfänger-Themen 4
S array 2 dimensional treppe Java Basics - Anfänger-Themen 3
S Array 2x2 Blöcke mit 0 und 1 Java Basics - Anfänger-Themen 10
C Array von Klassen Java Basics - Anfänger-Themen 2
julian0507 2Dim-Array Spaltensummen Java Basics - Anfänger-Themen 1
XWing Doppelte Zahlen im Array Java Basics - Anfänger-Themen 8
melisax Java 2D-Array Tabelle Java Basics - Anfänger-Themen 4
melisax Java Array Wert an bestimmtem Index angeben Java Basics - Anfänger-Themen 14
W Items löschen aus String Array vom Custom Base Adapter Java Basics - Anfänger-Themen 2
Proxy Stack erweitern mit neuem Array falls der alte voll ist!? Java Basics - Anfänger-Themen 5
E Array, nächste Zahl zur 5 ausgeben, wie? Java Basics - Anfänger-Themen 42
J Array.list vergleichen Java Basics - Anfänger-Themen 1
W Java-Code mit Array Java Basics - Anfänger-Themen 14
D Reflections & Generisches Array Java Basics - Anfänger-Themen 4
T Array Java Basics - Anfänger-Themen 2
T Array Java Basics - Anfänger-Themen 15
T Wörteranzahl im Array zählen Java Basics - Anfänger-Themen 9
Ostkreuz Zweidimensionaler Array Index Java Basics - Anfänger-Themen 2
S String Array Buchstaben um einen gewissen Wert verschieben Java Basics - Anfänger-Themen 4
R Images aus einem Array ausgeben Java Basics - Anfänger-Themen 3
R 2d Array individuell machen Java Basics - Anfänger-Themen 4
D 2D Char Array into String Java Basics - Anfänger-Themen 2
J Array Median bestimmen Java Basics - Anfänger-Themen 6
S Array Maximum bestimmen mit for und foreach Java Basics - Anfänger-Themen 7
S Prüfen ob ein zweidimensionales Array rechteckig ist Java Basics - Anfänger-Themen 4
N Array Java Basics - Anfänger-Themen 1
J Array Mittleren Wert bestimmen Java Basics - Anfänger-Themen 2
D OOP Array einem Objekt zuweisen Java Basics - Anfänger-Themen 2
O Zahlen aus einem char-array per char + Zeichen addieren Java Basics - Anfänger-Themen 2
S leeres Array statt Null Pointer Exception ausgeben Java Basics - Anfänger-Themen 20
S Inhalte aus Array vergleichen und Max ausgeben Java Basics - Anfänger-Themen 3
M 2d array ohne längen anlegen Java Basics - Anfänger-Themen 4
S Bestimmte werte aus einem Array löschen Java Basics - Anfänger-Themen 2
S Ausgeben wie oft ein Wert in einem Array vorkommt Java Basics - Anfänger-Themen 7
E Reihenfolge der Werte umdrehen (mittels statischem int-Array Java Basics - Anfänger-Themen 3
O 2 Dimensionales Array Java Basics - Anfänger-Themen 6
M Bubble Sort - Int[] Array sortieren Java Basics - Anfänger-Themen 2
javaBoon86 Array mehrere Dimensionen Java Basics - Anfänger-Themen 10
B Array nach Elementwerten sortieren? Java Basics - Anfänger-Themen 1
B Explizit Array definieren geht nicht? Java Basics - Anfänger-Themen 14
D Kleinste Zahl in Array finden die vorher noch errechnet werden müssen. Java Basics - Anfänger-Themen 4
L Gegebenes Array sortieren, indem zufällige Zahlenpaare aus Array ausgewählt werden Java Basics - Anfänger-Themen 14
Say 2-DIM Array Code lesen und verstehen Java Basics - Anfänger-Themen 5
N Array beim erstellen mit Werten füllen Java Basics - Anfänger-Themen 6
C Java Array Struktur, welche ist wann besser? Java Basics - Anfänger-Themen 12
Temsky34 Array IndexOf nicht verfügbar Java Basics - Anfänger-Themen 18
belana wie am besten 2D Array von String to Integer Java Basics - Anfänger-Themen 18
S Array mit Methode löschen Java Basics - Anfänger-Themen 2
J Java To String Methode, Array mit For-Schleife Java Basics - Anfänger-Themen 2
E Durch Muster in Array iterieren Java Basics - Anfänger-Themen 3
L Frage zum Array Java Basics - Anfänger-Themen 1
C 2D Array Ausgabe mit for-Schleife i,j Java Basics - Anfänger-Themen 4
D Methode: Array Reihenfolge tauschen Java Basics - Anfänger-Themen 3
julian0507 Array aus Methode in anderer Methode sichtbar machen Java Basics - Anfänger-Themen 10
P Array vom Typ Klasse Java Basics - Anfänger-Themen 18
Lion.King Array deklarieren und initialisieren Java Basics - Anfänger-Themen 5
P Array-Objekte-Aufruf Java Basics - Anfänger-Themen 22
A CSv.Datei einlesen und die werte in zweidemosional Int Array speichern Java Basics - Anfänger-Themen 9
M Methoden Zweidimensionaler Array mit Setter Methode ändern Java Basics - Anfänger-Themen 4
AkiJou Zeile in 2d Array löschen Java Basics - Anfänger-Themen 2
LilliCherry Array in einer Zeile ausgeben Java Basics - Anfänger-Themen 6
A Elemente in einem Array Java Basics - Anfänger-Themen 5
A Vorkommende Farben ermittel und als Array zurückgeben Java Basics - Anfänger-Themen 7
AhmadSlack Array Java Basics - Anfänger-Themen 7
Jambolo Kartenhand Array Java Basics - Anfänger-Themen 14
ravenz Schleife mit for über String Array „zahlen“und prüfen ob Wert „a“ oder „b“ oder „c“ entspricht (mittels || ) Java Basics - Anfänger-Themen 4
S Eine Variable in einem Array speichern Java Basics - Anfänger-Themen 5
T Methode, die prüft ob in einem Int-Array maximal 2 Zahlen enthalten sind, die größer als ihr Vorgänger sind Java Basics - Anfänger-Themen 5
T String Array Fehler beim Index Java Basics - Anfänger-Themen 3
krgewb byte-Array, das ein Bild repräsentiert Java Basics - Anfänger-Themen 1
I Methoden Wieso wird mein Array "a" verändert und meine Variable "a" nicht? Java Basics - Anfänger-Themen 4
EykS 3D Druckdatei basierend auf 3D Array? Java Basics - Anfänger-Themen 3
sserio Array funktioniert nicht Java Basics - Anfänger-Themen 2
sserio Iterierung über ein zweidimensionales Array Java Basics - Anfänger-Themen 16
sserio Zweidimensionales Array [][] wird untereinander ausgegeben Java Basics - Anfänger-Themen 14
Chris.089 2 Werte im Array tauschen Java Basics - Anfänger-Themen 6
D EinMalEins mithilfe einer for-Schleife und Array Java Basics - Anfänger-Themen 1

Ähnliche Java Themen

Neue Themen


Oben