Binäre Suche Fehler überall =(

[Mino1337]

Hallo,

Ich sollte im Rahmen einer Übung eine Binäre Suche in einem Array realisieren. Ich dachte ich hätte dies ziemlich Clever gelöst aber nun bekomme ich nur Fehlermeldungen array Index out of Bounds wo ich sie mir einfach nicht Vorstellen kann :noe: ...

Nimmt man den ersten Wert von Musikladen.java kommt beispielsweise Array Index put of Bounds in Z33 , 37 und 18 in BinaereSuche.java

Ich habe die Klassen BinaereSuche und Artikel geschrieben. Die Musikladendatei war vorgegeben. Die drei anderen Klassen die hierran beteiligt sind sind ebenfalls vorgegeben aber Unwichtig denke ich.


Musikladen

public class Musikladen {
    public static void main(String[] args){
        
        // Einlesen der Artikel in einen Array  
        String file = "artikelliste.dat";
        Artikel[] artikelliste = Parser.readArtikel(file);
        // Objekt der Klasse BinaereSuche erzeugen
        BinaereSuche binSuche = new BinaereSuche(artikelliste);
        
        System.out.println("*********************");
        System.out.println("*                   *");
        System.out.println("*   MUSIC MANiACS   *");
        System.out.println("*     PRO STORE     *");
        System.out.println("*                   *");
        System.out.println("*       xxxxO       *");
        System.out.println("*      xx  /xO      *");
        System.out.println("*     xx  / /x      *");
        System.out.println("*     x  / /xx      *");
        System.out.println("*      x/ /xx       *");
        System.out.println("*       xxxx        *");
        System.out.println("*                   *");
        System.out.println("*   ooo oo          *");
        System.out.println("*  o   o o     oo   *");
        System.out.println("*  0 x x ======xxo  *");
        System.out.println("*  o   o o     oo   *");
        System.out.println("*   ooo oo          *");
        System.out.println("*                   *");
        System.out.println("*********************");
        System.out.println();
        
        System.out.println("Willkommen zum MUSIC MANiACS Kassensystem!");
        System.out.println();
        System.out.println("Ausgabe des Katalogs:");
        System.out.println();
        System.out.println("Artikelnr. Hersteller Name");
        for(int i=0; i<artikelliste.length;i++){
            System.out.println(artikelliste[i].getArtikelnummer() + " " + artikelliste[i].getHersteller() + " " + artikelliste[i].getName());
        }
        System.out.println();
        
        System.out.println("Artikelscanner nicht gefunden.");
        System.out.println("Bitte um manuelle Eingabe.");
        System.out.println("Mit 'q' wird das Programm beendet.");
        System.out.println();
        
        String gesuchterArtikel = "anfang";
        int gesuchterIndex;
        Artikel gesucht;
        while(gesuchterArtikel.compareTo("q") != 0) {
            gesuchterArtikel = Terminal.askString("Artikelnummer manuell eingeben: ");
            System.out.println();
            gesucht = new Artikel(gesuchterArtikel);
            gesuchterIndex = binSuche.suche(gesucht);
            if(gesuchterIndex != -1){
                // in der folgenden Zeile wird die toString-Methode von 
                // artikelliste[gesuchterIndex] aufgerufen
                System.out.println("Daten des Artikels:\n" + artikelliste[gesuchterIndex]);
            }
            else{
                System.out.println("Artikelnummer ist nicht vorhanden!");
            }
            System.out.println();
        }
        
    }
}

BinaereSuche

public class BinaereSuche{

	
	private Artikel[] array;
	private int index;


	public BinaereSuche(Artikel[] p){
	this.array = p;
	}
	
	
	public int suche(Artikel suchObjekt){
	
	int a = 0;
	int m = array.length/2;
	int e = array.length;
	BS(suchObjekt,a,m,e);
	return index;
	}
	
	// Hier wird mittels Binaerer Suche nach dem Gewünschten Objekt gesucht
	public void BS(Artikel SO,int a, int m, int e){
	
	SO = SO;
	int anfang = a;
	int mitte = m;
	int ende = e;
	
	if (mitte>=array.length||array.length==0||mitte<0){
	index = -1;
	}
	if (array[mitte].compareTo(SO)==0){
	index = mitte;
	}
	if (array[mitte].compareTo(SO)>0){
	BS(SO,mitte+1,(anfang+ende)/2,array.length);
	}
	if (array[mitte].compareTo(SO)<0){
	BS(SO,anfang,(anfang+mitte)/2,mitte-1);
	}
	
	}
	
}

Artikel

public class Artikel  {
    
    // Attribute
    private String artikelnummer;
    private String hersteller;  
    private String name;
    private String kategorie;
    private double preis;
    
    // Konstruktoren
    public Artikel(String artikelnummer) {
        this.artikelnummer = artikelnummer;
    }
	
	public Artikel(String artikelnummer, String hersteller, String name, String kategorie, double preis) {
        this.artikelnummer = artikelnummer;
		this.hersteller = hersteller;
		this.name = name;
		this.kategorie = kategorie;
		this.preis = preis;
    }
	
	public String toString(){
	return "Name \t= "+this.name+
		   "Artikelnummer = \t"+this.artikelnummer+
		   "Hersteller = \t"+this.hersteller+
		   "Kategorie = \t"+this.kategorie+
		   "Preis = \t"+this.preis;
	}
    
    
    public int compareTo(Artikel o){
	int x = this.artikelnummer.compareTo(o.artikelnummer);
	return x;
	}
    
    
    // Getter
    public String getArtikelnummer() {
        return artikelnummer;
    }
    
    public String getHersteller() {
        return hersteller;
    }
    
    public String getName() {
        return name;
    }
}

Also kurz Musikladen erzeugt einen Array voll mit Artikel-Objekten der an ein BinaereSuche-Objekt übergeben wird.

Vielen Dank für eure Hilfe und Hinweise =)

 

[gescom]

Hi!

Falls dein gesuchtes Objekt kleiner als das mittlere ist suchst von anfang bis mitte-1, Andernfalls von mitte+1 bis ende. Ausserdem belegst du unnötig viele Variablen, benennen die Variablen doch gleich treffend. Für den Fall das der Artikel nicht vorhanden ist musst du dir auch noch etwas überlegen.

 

[X5-599]

Hier prüfst du, ob "mitte" ein gültiger index des "array"s ist.

if (mitte>=array.length||array.length==0||mitte<0){
    index = -1;
}

Danach gehst du aber gleich weiter und forderst mit diesem index ein Element aus dem "array" an. Egal, ob er gültig war oder nicht.

Ich würde sagen du brauchst nachdem du den "index" auf -1 gesetzt hast (ungültiger index) einfach nur ein "return".

So:

if (mitte>=array.length||array.length==0||mitte<0){
    index = -1;
    return;
}

Die weitere Logik habe ich mir nicht genauer angesehen. Kann sein, dass es noch weiterer Anpassungen bedarf...