Binäre Suche in einem array

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
vladima
User
Beiträge: 14
Registriert: Sonntag 23. April 2017, 14:58

Hey ihr Lieben,
ich habe wieder mal eine Frage :D
mein Code sieht so aus:

Code: Alles auswählen

a = [11,22,33,44,55,66,77] #meine Liste
x = 36#int(input("x = "))
mitte = len(a)//2 #die Mitte soll der int in der Mitte der Liste sein
links = 0 #wird festgesetzt
rechts = len(a) #ist das größte/letzte Element

while True: #damit er mir wieder die Schleife durchläuft
    if x == a[mitte]: #damit weiß ich ja schon, dass x drin ist und es passt.
        break
    else:	#hier scheints die Probleme zu machen
        if x > a[mitte]:
            links = mitte
        else:
            rechts = mitte - 1
        mitte = (links + rechts) // 2
    if x == a[links] or x == a[rechts - 1]: #bei Werten höher als 77 kommt er in eine Endlosschleife
        print (x,"ist drin")
        break

    if rechts == links: #funktioniert für einige, aber nicht alle Werte
        print ("ist nicht drin", x)
        break


bei den Anfangs- und Endwerten stimmt es, sobald ich aber zB nach 65 suchen lasse, ist es nicht mehr korrekt. Trotz debugger finde ich irgendwie meinen Fehler nicht... könnte mir da jemand einen Denkanstoß geben?

Liebe Grüße
Zuletzt geändert von Anonymous am Montag 15. Mai 2017, 19:30, insgesamt 1-mal geändert.
Grund: Quelltext in Python-Codebox-Tags gesetzt.
Benutzeravatar
noisefloor
User
Beiträge: 3843
Registriert: Mittwoch 17. Oktober 2007, 21:40
Wohnort: WW
Kontaktdaten:

Hallo,

willst du einfach nur herausfinden, ob der Eingabewert innerhalb von min und max deiner Liste liegt?

Gruß, noisefloor
vladima
User
Beiträge: 14
Registriert: Sonntag 23. April 2017, 14:58

noisefloor hat geschrieben:Hallo,

willst du einfach nur herausfinden, ob der Eingabewert innerhalb von min und max deiner Liste liegt?

Gruß, noisefloor
Ich will rausfinden, ob der eingegebene Wert in der Liste liegt. Also genau dieser Wert

Liebe Grüße
Benutzeravatar
noisefloor
User
Beiträge: 3843
Registriert: Mittwoch 17. Oktober 2007, 21:40
Wohnort: WW
Kontaktdaten:

Hallo

dann ist dein vorgehen aber arg kompliziert. Das geht ganz einfach mit dem in-Operator:

[codebox=pycon file=Unbenannt.txt]>>> my_list = [11, 22, 33, 44, 55, 66, 77]
>>> my_input = 36
>>> my_input in my_list
False
>>> my_input = 66
>>> my_input in my_list
True
>>>
[/code]

Gruß, noisefloor
vladima
User
Beiträge: 14
Registriert: Sonntag 23. April 2017, 14:58

noisefloor hat geschrieben:Hallo

dann ist dein vorgehen aber arg kompliziert. Das geht ganz einfach mit dem in-Operator:

[codebox=pycon file=Unbenannt.txt]>>> my_list = [11, 22, 33, 44, 55, 66, 77]
>>> my_input = 36
>>> my_input in my_list
False
>>> my_input = 66
>>> my_input in my_list
True
>>>
[/code]

Gruß, noisefloor
Ja, ich weiß, aber das ist leider die Vorgabe. Den Befehl kenne ich und das war auch unser erster Ansatz, aber es soll tatsächlich mit dem binären System programmiert werden und da habe ich irgendwo einen Fehler hin und ich komme einfach nicht dahinter :roll: Aber du hast recht,d as ist natürlich wesentlich leichter und schneller

Liebe Grüße!
BlackJack

@vladima: Ob ``in`` schneller ist hängt von der Python-Implementierung und der Datenmenge ab. Ab einer gewissen Datenmenge ist die binäre Suche auf jeden Fall schneller als naiv linear durchzugehen. Sonst wäre binäre Suche witzlos. Wenn es sich nicht um eine Hausaufgabe handelt, dann würde man übrigens einfach das `bisect`-Modul aus der Standardbibliothek dafür nehmen.

Was die Fehlersuche angeht: Mach das für 65 doch einfach mal ohne Programm manuell auf einem Blatt Papier und notiere bei jedem Schritt die Indexwerte. Und dann lass das Programm laufen, im Debugger schrittweise oder mit Ausgabe der Indexwerte bei jedem Schritt und schau wo das nicht mit Deinem Blatt Papier übereinstimmt. *Da* ist der Fehler.
vladima
User
Beiträge: 14
Registriert: Sonntag 23. April 2017, 14:58

Hallöchen ihr Lieben,

ich hab den Fehler gefunden. Das ganze auf Papier nachzurechnen war ziemlich klug :)
Danke!
zsanzhar
User
Beiträge: 19
Registriert: Samstag 17. Februar 2018, 21:28

Hallo, wo war das problem? ich kann nicht verstehen :(
Antworten