binaere Suche Verstaendnisproblem

[SebastianK]

Hallo,

mir geht es hier um keinen Quellcode - hoffe das ich dann den richtigen Bereich erwischt habe.
Mir geht es um das Prinzip wie die binäre Suche funktioniert und besonders darum ob nun die Indizes (bei den Rechnungen) berücksichtigt werden bzw. nach diesen gearbeitet wird.

hab jetzt ne ganze weile nach beispielen gesucht, nur gibt es bei vielen beispielen unstimmigkeiten in dem benutzen der indices (da wird dann einmal nach dem index gegangen und im nächsten schritt wieder nicht).

so ein beispiel:

Gesucht: 112
Index: 0 1- 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9
Wert: 4 6 18 32 55 61 87 112 115 150

1. Schritt:
- Wähle die Mitte: Länge = 10 => 10 / 2 = 5.
- Wähle Index 5 als Mitte. Index 5 hat den Wert 61.
- 61 < 112 => streiche die linke Seite (Index 5 eingeschlossen)

2. Schritt:
0 - 1 -- 2 - 3
87 112 115 150

- Mitte: Länge= 4 / 2 = 2
- Wähle Index 2 als Mitte. Index 2 hat den Wert 115.
- 115 > 112 => Nehme nur den Teil links von Index 2

3. Schritt:
0 - 1
87 112

- Mitte: Länge=2 / 2 = 1
- Wähle Indx 1 als Mitte, mit dem Wert 112

- Überprüfe 112 --> 112=gesuchterWert => Fertig.

112 liegt am Index 7.


Hab das alles mal aufgeschrieben um meine Denkweise darzustellen. Hoffe man verstehts.
Nun die Frage: Ist es so richtig?

Danke!

 

[schalentier]

Naja, bei der Suche bleibt das Array (oder die ArrayList) so wie sie ist, demnach veraendern sich die Indices nicht.

Demnach wuerd ich das so aufschreiben:

Index: 0 1- 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9
Wert: 4 6 18 32 55 61 87 112 115 150

min=0, max=9, mid=(max+min)/2=4
-> neues min=4

4 - 5 - 6 - 7 -- 8 - 9
55 61 87 112 115 150

min=4, max=9, mid=6
-> neues min=6

6 - 7 -- 8 - 9
87 112 115 150

min=6, max=9, mid=7
-> treffer, fertig

Also immer die Mitte ausrechnen, Wert dort ansehen und dann:
Falls wert[mid]<suchwert: neues min=mid
Falls wert[mid]>suchwert: neues max=mid
andernfalls bist du fertig.

 

[SebastianK]

danke für die antwort!

demnach veraendern sich die Indices nicht.

stimmt natürlich.

mid=(max+min)

da ist wohl mein fehler.

wäre es aber nicht besser die mitte nicht mit in das neue intervall zu nehmen oder ist das egal? die mitte wurde ja schon auf "<", ">" oder "=" dem gesuchten Wert überprüft.

 

[schalentier]

wäre es aber nicht besser die mitte nicht mit in das neue intervall zu nehmen oder ist das egal? die mitte wurde ja schon auf "<", ">" oder "=" dem gesuchten Wert überprüft.

Absolut korrekt. Irgendwie hab ich gespuert, irgendwas uebersehen zu haben