# Element in Array finden



## kulturfenster (19. Jun 2007)

Es gilt eine rekursive Methode zu schreiben, die ein bestimmtes Element in einem sortierten Array findet.

Die Vorlage sieht folgendermassen aus:


```
public int find(int[] a, int k)
	{
		
	}
```

Die schnellste mir bekannte Variante ist diejenige, die das mittlere Element des Arrays mit k vergleicht. Falls k noch nicht gefunden wurde, wird geprüft, ob es kleiner oder grösser ist. Je nach dem wird dann die untere oder die obere Hälfte des Arrays nochmals abgecheckt.

Mein Problem nun: Wie kann ich mit dieser Vorlage diesen Ansatz realisieren? Sollte ich dafür nicht noch ein Positionselement mitgeben?

Vielen Dank für Tipps!


----------



## The_S (19. Jun 2007)

Ein Positionselement benötigst du nicht. Finde deine Vorgehensweise soweit gut!


----------



## trazzag (19. Jun 2007)

Das klingt mir doch verdammt nach Hausaufgabe... ;-)



> Wie kann ich mit dieser Vorlage diesen Ansatz realisieren?



Wie du suchen willst, weißt du ja schon - versuch doch erstmal selbst ein wenig Code auf die Beine zu stellen und wenn du dann konkretere Fragen hast, wird dir bestimmt auch geholfen.


----------



## kulturfenster (19. Jun 2007)

nene, ich erwarte keine Lösung. Es ist eine Aufgabe, ja, aber keine Hausaufgabe.

Hier mein Versuch:

```
public int find(int[] a, int k)
	{
		int pos = a.length / 2;
		if(a[pos] == k) return pos;
		if(a[pos] < k) find(a, k-1);
		if(a[pos] > k) find(a, k+1);
		return -1;
	}
```
Was nun noch nicht stimmt, sind die rekursiven Aufrufe...


----------



## The_S (19. Jun 2007)

warum veränderst du k? Nach k wird noch gesucht ???:L . Schau dir mal System.arraycopy an!


----------



## Beni (19. Jun 2007)

Wie wäre es mit einer Schleife? Als Stichworte: while, for, ... :bae:


----------



## The_S (19. Jun 2007)

Beni hat gesagt.:
			
		

> Wie wäre es mit einer Schleife? Als Stichworte: while, for, ... :bae:



Ne, die Aufgabe ist es ja eine rekursive Methode zu schreiben


----------



## trazzag (19. Jun 2007)

vielleicht so in etwa (ungetestet):


```
public static int find(int[] a, int k)
	   {
	      int pos = a.length / 2;
	      
	      while(a[pos] != k) {

	    	  if(a[pos] > k) pos = pos / 2;  
		  if(a[pos] < k) pos = pos + (pos / 2);

	      }
	      
	      return pos;
	   }
```


----------



## The_S (19. Jun 2007)

trazzag hat gesagt.:
			
		

> vielleicht so in etwa (ungetestet):
> 
> 
> ```
> ...



Auch hier findet nie Rekursion statt :roll:


----------



## trazzag (19. Jun 2007)

Stimmt, und es funzt so eh nicht wirklich (gerade festgestellt).
Die zweite if-Zeile müßte eher so aussehen:


```
if(a[pos] < k) pos = pos + ((a.length - pos) / 2);
```


----------



## Scotty (19. Jun 2007)

schau mal, das scheint zu funktionieren.

```
public static int find(int[] a, int x) {
		try {
			return find2(a, x);
		} catch(Exception e) {
			return -1;
		}
	}
	
	private static int find2(int[] a, int x) throws Exception {
		int p = a.length / 2;
		if(x < a[p]) {
			if(p == 0) {
				throw new Exception();
			} else {
				int[] a_ = new int[p];
				System.arraycopy(a, 0, a_, 0, p);
				return find2(a_, x);
			}
		} else {
			if(a[p] < x) {
				if(p == 0) {
					throw new Exception();
				} else {
					int[] a_ = new int[a.length-p-1];
					System.arraycopy(a, p+1, a_, 0, a.length-p-1);
					return find2(a_, x) + p +1;
				}
			} else {
				return p;
			}
		}
	}
	
	public static void main(String[] args) {
		int[] a = new int[] { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 };
		System.out.println(find(a,0));
		System.out.println(find(a,22));
		System.out.println(find(a,1));
		System.out.println(find(a,21));
	}
```


----------



## The_S (19. Jun 2007)

Warum wollt ihr alle seine Aufgaben machen? Da lernt er doch dann gar nix mehr dabei, mal ganz davon abgesehen, dass 2 Methoden recht sinnfrei sind ...


----------



## Beni (19. Jun 2007)

Hobbit_Im_Blutrausch hat gesagt.:
			
		

> Beni hat gesagt.:
> 
> 
> 
> ...


Uooh, sorry


----------



## Scotty (19. Jun 2007)

ich weiß nicht, wie man es mit einer methode lösen kann, ohne eine indexvariable als parameter mitzuführen. wenn sich das element in der oberen hälfte befindet, muss der index als startwert mitgeführt werden. wird das element dann nicht gefunden, so würde -1 zurückgegeben und wegen der addition des startindex wieder erhöht was ein falsches ergebnis zur folge hätte. das ist eigentlich nicht ganz sauber, aber java erlaubt hier einfach eine exception zu werfen und den fehler später abzufangen. möglicherweise könnte man das auch über eine prüfung im rekursionsaufstieg ?(x > -1) umgehen, aber hierfür wäre zusätzlich eine bedingung pro rekursion und speicher für eine hilfsvariable  notwendig. außerdem gefällt mir diese variante besser.


----------



## The_S (19. Jun 2007)

Scotty hat gesagt.:
			
		

> ich weiß nicht, wie man es mit einer methode lösen kann, ohne eine indexvariable als parameter mitzuführen.



Nochmal System.arraycopy! Passe doch einfach dein Array an, dann klappts auch mit exakt dieser vorgegebenen Methode  .


----------



## Axion (19. Jun 2007)

Ich würde mein find nicht so implementieren das es ein aufsteigend sortiertes Array benötigt.



```
int[] tmp_ab = {6,5,4,3,2,1};
int[] tmp_auf = {1,2,3,4,5,6};
```

Beide Arrays sind für mich sortiert.


----------



## Eldar (19. Jun 2007)

Also entweder ist k die Indexvariable und nicht der gesuchte Wert, oder du benutzt wie der Hobbit im Blutrausch schon sagte einfach die Möglichkeit dein Array zu verändern. 
Da du bei jedem Durchlauf ja weißt, dass die Hälfte deines Arrays nicht mehr benötigt wird, kannst du diese auch einfach beim Methodenaufruf der nächsten Rekursion weglassen. Dein zu durchsuchendes Array verkleinert sich immer weiter.


----------



## trazzag (19. Jun 2007)

@Eldar:
Nein, du kannst das Array nicht einfach verkleinern, da er als Rückgabe ja die Position des gesuchten Wertes im ursprünglich übergebenen Array haben wollte...


----------



## Leroy42 (19. Jun 2007)

Hobbit_Im_Blutrausch hat gesagt.:
			
		

> Nochmal System.arraycopy! Passe doch einfach dein Array an, dann klappts auch mit exakt dieser vorgegebenen Methode  .



Jedesmal ein System.arraycopy zu machen ist ja nun total ineffizient.

Wer sagt denn, daß er *nur* die vorgegebene Methode benutzen darf?


```
public int find(int[] a, int k) {return find(a, k, 0, a.length-1);}
public int find(int[] a, int k, int from, int to) {
  if (to < from)
    return -1;
  int mid = (to+from) / 2;
  if (a[mid] == k)
    return mid;
  return k<a[mid] ? find(a, k, from, mid-1) : find(a, k, mid+1, to);
}
```
 
Achtung: Ungetestet!


----------



## kulturfenster (19. Jun 2007)

sieht so aus, als hätten hier einige ähnliche Probleme... 

Trotzdem danke für die rege Beteiligung. Ich bin nun auf dem richtigen Weg, hab aber leider noch nie mit arraycopy gearbeitet.

Wieso bekomme ich hier eine OutofBundsException?

```
if(a[pos] > k) {
			int[] a2 = new int[a.length/2];
			System.arraycopy(a, a[pos+1], a2, a2[0], a.length/2);
			find(a2, k);
		}
```

Nur zur Sicherheit: ArrayCopy allgemein: 
(welcher Array, von welcher Position, in welchen Array kopieren, an welche Position, wieviele Elemente)
stimmt das so?


----------



## kulturfenster (19. Jun 2007)

> Jedesmal ein System.arraycopy zu machen ist ja nun total ineffizient.


wieso?


> Wer sagt denn, daß er nur die vorgegebene Methode benutzen darf?


Ich glaube, es ist schon so gemeint, dass ich nur eine Methode verwende. Das Kopieren bzw. Verkleinern des Arrays scheint glaub schon die richtige Antwort zu sein...


----------



## The_S (20. Jun 2007)

kulturfenster hat gesagt.:
			
		

> Nur zur Sicherheit: ArrayCopy allgemein:
> (welcher Array, von welcher Position, in welchen Array kopieren, an welche Position, wieviele Elemente)
> stimmt das so?



Steht alles in dem API  .

1. Parameter = Ursprüngliches-Array
2. Parameter = ab wo wird vom ursprünglichen Array aus kopiert (indieces fangen bei 0 an)
3. Parameter = Array, in das kopiert werden soll
4. Parameter = ab wo wird in das neue Array kopiert
5. Parameter = Wie viel wird kopiert



			
				trazzag hat gesagt.:
			
		

> @Eldar:
> Nein, du kannst das Array nicht einfach verkleinern, da er als Rückgabe ja die Position des gesuchten Wertes im ursprünglich übergebenen Array haben wollte...



Kann man wohl, du kannst halt nur nicht einfach dein letztes Ergebnis zurückgeben, sondern musst ein bisschen rechnen.



			
				Leroy42 hat gesagt.:
			
		

> Hobbit_Im_Blutrausch hat gesagt.:
> 
> 
> 
> ...



Das es effizient ist, habe ich nie behauptet. Aber das ist die einzige Möglichkeit, wenn nur dieser Konstruktor und sonst nichts verwendet werden darf, was man imho aus der Aufgabenstellung raus so interpretieren kann!


----------



## The_S (20. Jun 2007)

```
public static int find(int[] a, int k) {
	      
		   int middle = a.length / 2;
		   if (a[middle] == k) {
			   return middle;
		   }
		   else if (a[middle] > k) {
			   int[] temp = new int[middle];
			   System.arraycopy(a, 0, temp, 0, temp.length);
			   return find(temp, k);
		   }
		   else {
			   int[] temp = new int[a.length - middle];
			   System.arraycopy(a, middle, temp, 0, temp.length);
			   return middle + find(temp, k);
		   }
	   }
```

Ebenfalls ungetestet, setzt voraus, dass die gesuchte Zahl auch wirklich im Array enthalten ist!


----------

