Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Rekursive binäre Suche programmieren » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Rekursive binäre Suche programmieren
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
InformatikN00bine
Grünschnabel


Dabei seit: 07.04.2016
Beiträge: 2

Rekursive binäre Suche programmieren Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Hallo, ich habe folgende Aufgabe:

Implementieren eine Suchfunktionalität, die aus einer sortierten Liste die Position
eines gegebenen Elementes k zuruckliefert, falls das Element vorhanden ist. Sonst ¨
gebe -1 zuruck. Nutzen Sie dabei folgendes Prinzip: ¨
1. Falls Liste leer, endet die Suche erfolglos, sonst betrachte A[m] an mittlerer
Position der Liste
2. Falls k = A[m] => fertig
3. Falls k < A[m] => durchsuche linke Teilliste nach demselben Verfahren
4. Falls k > A[m] => durchsuche rechte Teilliste nach demselben Verfahren
Hinweis: Es ist also eine rekursive Implementierung gefragt.

Bislang habe ich:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
public static int elementPosition(int[] arraySortiert, int k) {
		if (arraySortiert.length == 0) {
			return -1;
		}
		int half = arraySortiert.length/2;
		if(k==arraySortiert[half]) {
			return half;
		} else if(k<arraySortiert[half]) {
			return ?;
		} else {
			return ?;
		}
		return -1;
	}


Mein Problem ist nun, dass ich ja, wenn ich links weitersuche, dann zu arraySortiert.length/4 gehen müsste und wenn ich rechts weitersuche dann arraySortiert.length*3/4... links die richtige position könnte ich kriegen, indem ich einen neuen halb so langen array erstelle mit den ersten elementen aus dem ursprünglichen und im rekursiven aufruf den dann übergebe. aber für nach rechst suchen klappt das nicht...

oder muss ich bereits von vornherein die länge des arrays übergeben in die funktion? dann müsste ich die länge natürlich vorher schon wissen... ich hätte jetzt halt gedacht, dass ich nur den array und das k bekomme...
19.04.2016 13:20 InformatikN00bine ist offline Beiträge von InformatikN00bine suchen Nehmen Sie InformatikN00bine in Ihre Freundesliste auf
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

An die Funktion musst du das Array sowie die rechte und linke Grenze des zu durchsuchenden Intervalls übergeben.

__________________
Syntax Highlighting fürs Board (Link)
19.04.2016 21:25 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Rekursive binäre Suche programmieren