Rekursive binäre Suche programmieren |
19.04.2016, 13:20 | Auf diesen Beitrag antworten » | |||||
InformatikN00bine | Rekursive binäre Suche programmieren 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:
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, 21:25 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | An die Funktion musst du das Array sowie die rechte und linke Grenze des zu durchsuchenden Intervalls übergeben. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|