Element in Array finden

[kulturfenster]

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]

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

 

[trazzag]

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]

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]

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

 

[Beni]

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

 

[The_S]

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

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

 

[trazzag]

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]

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

Auch hier findet nie Rekursion statt :roll:

 

[trazzag]

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]

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]

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]

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

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

Uooh, sorry

 

[Scotty]

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]

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]

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]

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]

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

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]

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]

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]

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

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

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?

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]

	   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!