Array rekursiv untersuchen

[babuschka]

Hallo, ich schon wieder.

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]

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

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]

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.

 

[babuschka]

Ist gar nichts von minm Ansatz brauchbar?

Wi lauf ich denn ohn jede Schleife durch das Array?

 

[bERt0r]

Ich schätze mal du willst folgendes machen: Binäre Suche ? Wikipedia

 

[Final_Striker]

Wi lauf ich denn ohn jede Schleife durch das Array?

z.B. so:

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

 

[Spacerat]

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

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

 

[babuschka]

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]

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

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

 

[babuschka]

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

 

[langhaar!]

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.

 

[Spacerat]

@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. )... Wenn sie nicht funktioniert, weisst du hoffentlich, an welchem Teil du noch was ändern darfst.

 

[babuschka]

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:

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


}

 

[Firephoenix]

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]

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.

 

[Spacerat]

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 ).
[EDIT]Man war des spät Gestern...

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]

 

[babuschka]

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

 

[Spacerat]

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]

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?

 

[Spacerat]

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]

 

[babuschka]

Okay, damit funktionieren alle Fälle, danke.

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

Es kommt doch das Gewünschte jeweils heraus.

 

[Spacerat]

du bekommst jetzt den negierten EndIndex -2 (statt -1).
[EDIT]Ach ja... machst du noch 'n "Erledigt" an den Thread, büdde?[/EDIT]