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:
Kompletter Code:
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);
}
}
