Array, lineare Suche, binäre Suche, Programm bleibt unerwartet stehen...

[Neo Larson]

Guten Abend,

ich habe ein Programm geschrieben, welches:

1. die Slot-Anzahl für ein Array bekommt
2. ein eigenes Objekt vom Typ IntArray erzeugt und die Anzahl an den Konstruktor des IntArray-Objekts weitergibt
3. der Konstruktor startet eine Methode zur Eingabe der Array-Werte, anschließend werden diese ausgegeben
4. der Konstruktor startet eine Methode, die die Werte aufsteigend ordnet, anschließend wieder Ausgabe

5. die main-Methode fragt nach der zu suchenden Zahl
6. in der main wird die lineare Suche gestartet und der gefundene Slot zurückgegeben
Falls ja, wird eine rekursive binäre Suche anschließend eine iterative binäre Suche gestartet
Falls nein, wird "Element nicht gefunden" ausgegeben.
7. die main fragt nach einer weiteren Suche
Falls ja, gehts bei 5. weiter
Falls nein, wird das Programm beendet


Nun zu meinem Problem:

Das Programm bleibt nach mehrmaligem Suchdurchlauf bei Punkt 6 nach der rekursiven binären Suche stehen.

Die Klasse IntArray, die mit der main getestet wird.

import java.util.Scanner;                            // Scanner-Klasse wird fuer die Eingabe benoetigt

class IntArray
{
    // Instanzvariable
    int[] array;

    // Konstruktor
    IntArray(int index)
    {
        array = new int[index];

        werteRein();
        printArray();
        ordnenArray();
        printArray();
    }

    // Methoden

    /* Die Methode werteRein() wird vom Konstruktor verwendet, um 
       das Array zu befuellen */
    void werteRein()
    {
        Scanner scan = new Scanner(System.in);

        for(int slot=0; slot<array.length; slot++)
         {
            System.out.print("Den " +(slot+1)+ ". Wert eingeben: ");
            array[slot]=scan.nextInt();
        }
    }

    /* Die Methode ordnenArray() wird vom Konstruktor verwendet, um
       das gefuellte Array aufsteigend zu sortieren */
    void ordnenArray()
    {
        int temp, min;
        int slot3=0;

        System.out.println("\nDie Zahlen werden geordnet!");

        for(int slot1=0; slot1<array.length; slot1++)
         {
            temp=array[slot1];
            min=array[slot1];

            for(int slot2=slot1; slot2<array.length; slot2++)
             {
                if(array[slot2]<min)
                {
                    min=array[slot2];
                    slot3=slot2;
                }

            }
            array[slot1]=min;
            if(min!=temp)
                array[slot3]=temp;
        }
    }

    /* Die Methode linSuche() sucht innerhalb des Arrays nacheinander
       alle Elemente nach dem zu suchenden Element ab */
    int linSuche(int ziel)
    {
        for(int slot=0; slot<array.length; slot++)
         {
            Integer arraySlot = new Integer(array[slot]);
            if(arraySlot!= null )
                if(ziel==array[slot])
                    return slot;
        }
        return -1;
    }

    /* Die Methode binSuche() sucht innerhalb des Arrays
       mithilfe einer rekursiven binaeren Suche nach dem zu suchenden
       Element */
    int binSuche(int start, int ende, int ziel)
    {
        int mittel = (start + ende)/2;

        if(array[mittel]==ziel)
            return mittel;

        if(start==ende)
            return -1;

        if(array[mittel]>ziel)
            return binSuche(start, mittel-1, ziel);

        return binSuche(mittel+1, ende, ziel);
    }

    /* Die Methode binSuche() sucht innerhalb des Arrays
       mithilfe einer iterativen binaeren Suche nach dem zu suchenden
       Element */
    int binSucheIter(int start, int ende, int ziel)
    {
        int mittel=(start+ende)/2;

        while(array[mittel]!=ziel)
        {
            mittel=(start+ende)/2;

            if(start==ende)
                return -1;

            if(array[mittel]>ziel)
                mittel-=1;

            start=mittel;
        }

        return mittel;
    }

    /* Die Methode printArray() gibt alle Array-Elemente
       vor und nach dem Ordnen auf dem Bildschirm aus */
    void printArray()
    {
        System.out.println();

        for(int slot=0; slot<array.length; slot++)
         {
            System.out.print(array[slot]);

            if(slot<(array.length-1))
                System.out.print(", ");
        }
        System.out.println();
    }
}

Die main-Methode

public class TestLinSuche
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);

        int anzahl, gesucht, gefunden;
        int suche=1;

        System.out.print("\nWie viele Slots soll das Array bekommen: ");
        anzahl=scan.nextInt();

        IntArray arr1 = new IntArray(anzahl);

        while(suche == 1)
        {
            System.out.println("\nNach welcher Zahl möchten Sie suchen: ");
            gesucht=scan.nextInt();

            gefunden=arr1.linSuche(gesucht);

            if(gefunden >= 0)
            {
                System.out.println("\nDie Zahl ist auf Slot " +gefunden);
                System.out.println("\nRekursive binaere Suche: " +arr1.binSuche(0, anzahl-1, gesucht));
                System.out.println("Iterative binaere Suche: " +arr1.binSucheIter(0, anzahl-1, gesucht));
            
            }
            else
                System.out.println("\nElement nicht gefunden!");

            System.out.println("\nMöchten Sie eine weitere Zahl suchen?\nJa: 1\nNein: 0");
            suche=scan.nextInt();

            while(suche!=1)
            {
                if(suche!=0)
                {
                    System.out.println("Nur zwischen 1 und 0 waehlen.");
                    suche=scan.nextInt();
                }
                else
                    System.exit(0);
            }
        }
    }
}

Kann mir eventuell einer sagen, ob ich was übersehen und/oder was falsch hab?

Vielen Dank
Neo</array.length;></array.length;></min)
</array.length;></array.length;></array.length;>

 

[Machareder]

Kann mir eventuell einer sagen, ob ich was übersehen und/oder was falsch hab?

Du hast etwas in deiner binSucheIter() Methode falsch.

 

[Neo Larson]

Kannst du mir sagen was?
Finde den Fehler irgendwie nicht...

 

[VfL_Freak]

Moin,

außerdem: was bedeutet "das Programm bleibt stehen" ??
Da kommt doch sicher in der Konsole ein Fehler!
Poste den StackTrace !!

Gruß Klaus

 

[Neo Larson]

Nee, kommt kein Fehler.
Das Programm läuft, hab drei von 8 Zahlen getestet (1, 2, 6, ...)
Beim dritten Durchlauf (bei der 6) bleibt das Programm einfach stehen.

Quasi zwischen beiden Bildschirmausgaben, während das Programm läuft:
System.out.println("\nRekursive binaere Suche: " +arr1.binSuche(0, anzahl-1, gesucht));


System.out.println("Iterative binaere Suche: " +arr1.binSucheIter(0, anzahl-1, gesucht));

Da kommt nichts. Als ob es abstürzt...

 

[Joose]

Beim dritten Durchlauf (bei der 6) bleibt das Programm einfach stehen.

Nein es bleibt nicht stehen, sondern es läuft weiter und arbeitet deinen programmierten Code ab!
Das Problem liegt daran das deine Logik falsch ist. Gib am Anfang der Methode "binSuche" eine Konsolen-/Logmeldung aus.
Du wirst sehen das dein Programm einfach die Methode "binSuche" abarbeitet dabei sich aber wahrscheinlich in eine "Endlosrekursion" verrennt.

 

[Neo Larson]

Habe den Code geändert und er funktioniert nun

    int binSucheIter(int start, int ende, int ziel)
    {
        int mittel;

        while(ende >= start)                        // Solange das Array-Ende groeßer oder gleich dem Array-Start
        {
            mittel=(start+ende)/2;                    // Berechnet den Mittelwert

            if(ziel < array[mittel])                // Das Ziel-Element ist auf der linken Seite, suche dort weiter
                ende=mittel-1;
            else                            // Das Ziel-Element ist auf der rechten Seite, suche dort weiter
                start=mittel+1;
             if(ziel == array[mittel])                // Das Ziel-Element entspricht dem Mittelwert
                return mittel;                    // und der passende Slot wird zurueckgegeben
        }
        return -1;                            // Das Ziel-Element wurde nicht gefunden
    }

Vielen Dank für Eure Unterstützung