Binäre-Suche Algorithmus


slitec

Grünschnabel
#1
Hallo.

Hier habe ich eine Binäre-Suche programmiert. Hierbei sollen z.B. 2 zufällige Zahlen (schritte1) wie z.B. die Zahl 30 und 50 insgesamt X mal gesucht werden (schritte2). Jeweils soll dabei ein Mittelwert der Zeit berechnet werden.

Mir ist nun aufgefallen, dass manche Zahlen nicht mal erst gesucht werden. So produziert der Zufallsgenerator eine zufällige Zahl wie z.B. 143 und die Suche beginnt. Ist eine Zahl gefunden worden, so soll diese die Meldung:
"Suchzahl3: 1989 Zeit: 683350 Schritte: 7"
ausgeben.
Allerdings bekomme ich auch folgende Meldungen:
Suchzahl4: 1748 Zeit: 600 Schritte: 0
Suchzahl5: 1049 Zeit: 550 Schritte: 0
Suchzahl6: 20 Zeit: 600 Schritte: 0
Suchzahl7: 334 Zeit: 600 Schritte: 0
Suchzahl8: 669 Zeit: 600 Schritte: 0

obwohl sich diese Zahlen im Array befinden ? Woran könnte dies liegen?

Binäre-Suche Algorithmus:

Java:
public int suche(int suchzahl) {
           
            int mitte;
            rechts = liste.length-1; // z.B. 0-99 Zahlen --> 99/2 = 49
           
       
            while(suchzahl >= liste[links] && suchzahl <= liste[rechts]) {
               
                mitte = (links + rechts) /2;
                schritte++;
               
               
                if( suchzahl>liste[mitte]) {
                    links = mitte +1;
           
                    }
                else if ( suchzahl < liste[mitte]) {
                    rechts = mitte -1;
           
                    }
                else {
                   
                    return mitte;}
               
            }
           
            return -1;  
           
            }

Kompletter Code:

Java:
// BINÄRE SUCHE !!!


package a3;
import java.util.Arrays;
import java.util.Random;


public class test
{
     int[] liste; //Array wird definiert als "liste"
     Random zufall = new Random();    // wird erzeugt für Klasse erzeugenUnsortiert()
     int suchzahl; //Dies ist die gesuchte Zahl
     int plätze;
     int links=0; // linker Index
     int rechts; // rechter Index
     int schritte;
     int schritteSum; //Summe aller Schritte
   
     public test() {
       
     }
   
   
     public void erzeugeZufallszahl(int plätze,int oberGrenze) {
            //Erzeugt nicht gleichverteilte Zufallszahlen (doppelte sind möglich)
           
             this.plätze= plätze-1;
            liste = new int [plätze];
            //Anzahl an Plätze wird übergeben
           
            for (int i=0; i<liste.length;i++) {
                liste[i] = zufall.nextInt(oberGrenze);
                // Liefert eine int-Pseudo-Zufallszahl im Bereich von 0 bis oberGrenze
            }
           
        }
   
   
   
     public void sortieren(){
            Arrays.sort(liste);
        }
   
   
        public void ausgabe() {
            for (int i=0; i<liste.length; i++) {
                System.out.println("Zahl: "+ liste[i] + " || Index: " + i);
            }
        }
       
       
                                   
        public int suche(int suchzahl) {
           
            int mitte;
            rechts = liste.length-1; // z.B. 0-99 Zahlen --> 99/2 = 49
           
       
            while(suchzahl >= liste[links] && suchzahl <= liste[rechts]) {
               
                mitte = (links + rechts) /2;
                schritte++;
               
               
                if( suchzahl>liste[mitte]) {
                    links = mitte +1;
           
                    }
                else if ( suchzahl < liste[mitte]) {
                    rechts = mitte -1;
           
                    }
                else {
                   
                    return mitte;}
               
            }
           
            return -1;  
           
            }
           
           
           
       
       
       
public long suchzeitBinaer(int schritte1,int schritte2, int warmup) { //schritte1 = 30 , schritte2= 1000
           
            for(int y=0; y<warmup; y++) {
                suchzahl = 0;
                suche(suchzahl);
               
            }
           
           
            long zeit1=0; //Zeit für 30 Suchen
           
            for (int x=0; x<schritte1;x++) {
            long    zeit2=0;; // Zeit für 1000 Suchen
           
            suchzahl = liste[zufall.nextInt(liste.length)];
           
            for (int j=0; j<schritte2;j++ ) {
               
                final long timeStart = System.nanoTime();
                suche(suchzahl);
                final long timeEnd = System.nanoTime();
                long zeit = timeEnd - timeStart;
                zeit2 += zeit; //Zeit innere Schleife addiert
               
            }
            zeit1 += zeit2/schritte2; //Zeit äußere Schleife addiert
            System.out.println("Suchzahl"+x+": " +suchzahl+"      Zeit: "+zeit2/schritte2+"      Schritte: "+schritte);
            schritteSum += schritte;
            schritte=0;
       
            //Für Anzahl an schritte2 wird die Zeit wiedergegeben sowie die Schritte
       
            }
           
            long zeitFinal=zeit1/schritte1; //Finale-Zeit
            System.out.println("Suchzeit: "+zeitFinal+" Nanosek." + " gesamte Schritte: "+schritteSum);
            return zeitFinal;
        }
           
           
       
        public void ausgabe1() {
            for (int i=0; i<liste.length; i++) {
                System.out.println(liste[i] + " || Schritt: " + (i+1));
            }
        }
       
       
               
       
   
    public static void main(String[] args)
    {
    test b1 = new test();
    b1.erzeugeZufallszahl(1000, 2000);
    b1.sortieren();
//    b1.ausgabe();
    b1.suchzeitBinaer(10, 2, 5);
   

   
   

   
    }
}
 

slitec

Grünschnabel
#2
Ok hab es selbst gefunden.
Ich hatte den Linken bereicht nicht auf 0 gesetzt nach jeder Suche. Somit wurden die Werte immer weiter übernommen.
 

Neue Beiträge