✔ Binäre suche

[kle-ben]

Hi!
Ich will ein Programm mit VBA schreiben das eine Zufallszahl zwischen 0 und 1000
generiert und dann diese Zahl durch ein binäres suchsytem bestimmt. Die Zahl ist
generiert und ich hab eine Variable zur Feststellung ob die generierte Zahl größer oder kleiner ist als die geratene. Aber wie definiere ich jetzt den nächsten Bereich der überprüft werden soll. Ich hoffe ich hab es ist verständlich.
Gruß Benny

 

[kle-ben]

Hat keiner ne Antowrt, oder hab ich das zu umständlich erklärt
plz
Gruß

 

[Shakie]

Also für mich hast du es zu umständlich erklärt ^^
Was meinst du denn mit "binäres Suchsystem"?

 

[kle-ben]

Hi!
Also bei einer binären suche wirt etwas durch halbiern gesucht.
Beisiel:
Du suchst im Telefonbuch nach dem Namen Ratke dann schlägst du es in der Mitte
auf.Dann landest du bei dem Buchstaben M. R ist aber größer als M also Hlbierst du den hintern Teil wieder. Und kommst zum Buchstaben S. R ist nun kleiner als S und somit muss der Bereich zwischen M und S nochmals halbiert werden. Nun lndet man bei P und stellt fest das R größer ist. .........
Wenn man das nun weiterhin so macht kommt man irgendwann zu dem Buchstaben R.
Bei mir sollen das ganze halt jetzt mit Zahlen stattfinden.
Mein Problem hier an einem Beispiel:
Suche die zahl 300 aus 1000
ich überprüfe bei 500 die Zahl ist kleiner / ich halbiere
also überprüfe ich 250 die Zahl ist größer
ich muss nun die nächste zahl so bestimmen das sie in der Mitte von
250 und 500 liegt also 375 einfaches * 1.5 nehmen hilft hier nicht
das wird hierraus jetzt hoffentlich klar
ich stelle also fest das 300 kleiner ist als 375
wenn ich nun 375 halbiere kome ich auf 183
ich muss aber den bereich zwischen 250 und 375 halbiern
weil kleiner als 250 ist 300 ja nicht

Ich hoff mein Problem ist hierdurch etwas deutlicher geworden.
Es liegt irgendwo bei der übergabe von Variablenwerten.
Ich hab das ja schon ziemlich weit gedacht aber irgendwie komm ich nicht weiter.
Gruß Benny

 

[RedWing]

Hallo das ist ganz einfache binäre Suche:

Ich kenn mich in VB nicht aus aber folgender Pseudocode solltes auch tun:

procedure guess
begin

        Initialisiere Zufallszahl;
        var random = nächste Zufallszahl aus 0 und 1000;
        var min_element = 0;
        var max_element = 1000;
        var gefunden = falsch;

        solange( nicht gefunden)
        do
                var mitte = (min_element + max_element) / 2;  //ermittle die mitte aus der gegebenen Suchbreite
                if(mitte == random)
                then
                        Gebe aus: "Gefunden";
                        gefunden = wahr;
                else 
                        if( mitte < random)  //Suche rechts weiter
                        then
                                min_element = mitte + 1;
                        else                 //Suche links weiter
                                max_element = mitte - 1;
                        fi
                fi
        done
end

 

[kle-ben]

Danke das ist schon mal sehr hilfreich.
Nur ich versteh den Teil mit der Variable Mitte noch nicht so ganz.
Wieso wird die um eins erhöt bzw verringert bie definiert sich dadraus
der neue halbierte zu überprüfende Bereich.
Also wo genau ist mein denkfehler?
Danke
Gruß Benny

 

[RedWing]

Wieso wird die um eins erhöt bzw verringert bie definiert sich dadraus
der neue halbierte zu überprüfende Bereich.

Nicht die Variable mitte wird um eins erhöht, sondern das neue min bzw
max_element, ergibt sich aus der mitte + 1 je nachdem ob die errechnete mitte
größer bzw kleinergleich dem gesuchten Element random ist, sprich ob rechts
oder links im neuen Schleifendurchlauf gesucht werden soll:

                zu suchender Wert random
0...............263......................................................................1000

Anfang der Suche:

min_element                             erste mitte(min_element + max_element/2)         max_element
0.......................................500..............................................1000                   
mitte > random
=>
neues max_element ist jetzt mitte - 1
=>
min_element                             neue mitte(min_element + neues max_element/2)    neues max_element
0.......................................250..............................................499

mitte < random
=>
neues min_element ist jetzt mitte + 1
=>
neues min_element                       neue mitte(neues min_element + max_element/2)    max_element
251.....................................375..............................................499

usw

Gruß

RedWing

 

[kle-ben]

Hm stimmt! Vielen Dank soweit.
Nur was ich noch nicht ganz verstehe für was genau die +1 und die -1 sind,
also was die genau im Programm ausmachen. Ohne sie funktioniert es auch,
nur tritt dann folgendes Problem auf:
260 wird sowohl mit den einsen als auch ohne sie in 9 Schritten berechnet.
0 wird mit den einsen in 9 Schritten ohne sie aber in 11 Schritten berechnet.
Woran liegt das?
Gruß Benny

 

[RedWing]

Hallo,

Hm stimmt! Vielen Dank soweit.
Nur was ich noch nicht ganz verstehe für was genau die +1 und die -1 sind,
also was die genau im Programm ausmachen. Ohne sie funktioniert es auch,
nur tritt dann folgendes Problem auf:

min_element = mitte + 1; bzw
max_element = mitte - 1; ergibt sich deswegen da du ja
mitte schon abgehandelt hast.
Sprich nehmen wir an die Mitte ist 500.
Somit hast du 500 schon verglichen. Wieso solltest du dann im nächsten Schritt 500 nochmal
als min bzw max Element zu Rande ziehen? Deswegen macht es Sinn mit 499 als max_element bzw 501 als min_element weiter zu machen...

Ohne dem gehts natürlich auch, wäre aber doppelt gemoppelt...

Gruß

RedWing

 

[kle-ben]

Ok jetzt hab ichs.
Vielen Dank für deine Hilfe,
und noch ein par schöne Feiertage.
Gruß Benny