Kleinsten Index in Array finden

[Maxpower123]

Hi,

ich soll ein Programm schreiben, das den kleinsten Index in einem Array findet bzw. den Index der zum kleinsten Wert im Array gehört.

Mein Programm sieht so aus:

public static void main(String[] args) {

        double[] arr = { 5, 3, 8, 2, 4 };     

        System.out.println(minIndex(arr, 0, 4));

    }

    public static int minIndex(double[] arr, int startIndex, int endIndex) {

             
        if (arr[startIndex] < arr[endIndex]) {
            minIndex(arr, startIndex, endIndex-1);
        }
     
        if (arr[startIndex] > arr[endIndex]) {
            minIndex(arr, startIndex+1, endIndex);
        } 
     
        if (startIndex == endIndex) {
            System.out.println(startIndex);
            return startIndex;
         
        }
     
     
        return startIndex;
     
    }

Beim Debuggen habe ich herausgefunden, dass das Programm zwar den richtigen Index findet, aber dann wieder beide Indizes zurückzählt, so dass letztlich immer 0 als Ergebnis berechnet wird.

Die Konsolenausgabe sieht so aus:

3
0

Also in dem If-Statement wird noch die 3 ausgegeben, an die main-Methode wird allerdings 0 zurückgegeben, was ich nicht ganz verstehe.

Kann mir vielleicht jemand sagen, woran das liegt?

Gruß und danke im Voraus

 

[Jardcore]

Hey Maxpower123,

du hast einfach vergessen die < und > Varianten auch mit return zu beenden. In deinem Fall wird mehrfach nun parallel die Methode minIndex() aufgerufen. Also return minIndex(...); nicht vergessen.

Hast du den JavaDebuger benutzt?

Beste Grüße,
Jar

 

[Meniskusschaden]

Das liegt daran, dass die Rückgabewerte deiner rekursiven Aufrufe nicht stimmen. Du gibst immer startIndex zurück. Für die tiefste Aufrufebene ist das auch korrekt, denn da hast du das Minimum ja gefunden. Aber bei den vorherigen Aufrufebenen ist es falsch, denn startIndex ist auf der jeweiligen Ebene ja noch nicht korrekt. Stattdessen musst du das Ergebnis von minIndex zurückgeben.

Ein zweiter Punkt ist noch nicht ganz sauber. Falls es zwei gleiche Elemente gibt, funktioniert das Programm nicht korrekt.

 

[Maxpower123]

Danke für die schnellen Antworten.

Das Programm funktioniert jetzt so:

public static void main(String[] args) {

        double[] arr = { 2, 3, 2, 5 };
      

        System.out.println(minIndex(arr, 0, 3));
      
      

    }

    public static int minIndex(double[] arr, int startIndex, int endIndex) {
      
      
     
              
        if (arr[startIndex] < arr[endIndex]) {
            return minIndex(arr, startIndex, endIndex-1);
        }
      
        if (arr[startIndex] > arr[endIndex]) {
            return minIndex(arr, startIndex+1, endIndex);
        }  
      
        if (startIndex == endIndex) {          
            return startIndex;          
        }       

  if (arr[startIndex] == arr[endIndex]) {
            return -1;
        }
      
        return startIndex;
      
    }

 

[Jardcore]

Du könntest auch eine Exception werfen, damit die Behandlung auch gleich abgefrühstückt ist und du das nicht weiter oben machen musst, indem du dann auf -1 prüfst.

Weiterhin kannst du als Vorbedingung definieren, dass nur eine Menge, also keine doppelten Elemente, vorhanden sein dürfen. Das kommt dann aber auch auf den Kontext an.

 

[kneitzel]

Also wieso ist der Wert -1 denn gerechtfertigt? Nur weil zwei Werte gleich sind, heisst es doch nicht, dass es keinen kleinsten Wert gibt. Und selbst wenn die beiden Elemente das kleinste Element gewesen wären (dann gäbe es kein eindeutiges Ergebnis) würde ich die Beschreibung so anpassen, dass ein Index des kleinsten Elements zurück gegeben wird.

Eine Exception und eine -1 Rückgabe sehe ich als nicht wirklich gerechtfertigt an.

Die Lösung könnte also sein, im ersten if statt ein < ein <= zu prüfen. Und was ganz existenziell für alle rekursiven Implementationen ist: Pack bitte die Prüfung des Abbruchbedingung wenn möglich immer an den Anfang! Also bitte das if (startIndex == endIndex) als allererstes ausführen!

 

[Viktim]

eine Frage hab ich, warum nimmst du nicht einfach eine Schleife?