Problem mit binärem Einfügen

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
Unplayable
User
Beiträge: 51
Registriert: Mittwoch 24. Februar 2016, 22:09

Hallo Zusammen,

ich möchte ein Programm schreiben, welches eine bereits aufsteigend sortierte Liste und eine Zahl übergeben bekommt. Die Liste soll dann halbiert werden und die Zahl soll entweder in die linke oder rechte Hälfte eingefügt werden. Als Beispiel nehme ich jetzt einmal die Liste [1,2,3,4,5,6] und die Zahl 2. Das funktioniert mit meinem Code auch richtig und ich bekomme als Ausgabe: [1,2,2,3,4,5,6]

Code: Alles auswählen

def binaeres_einfügen(liste,zahl):

    sort = liste

    links  = sort[0:len(sort)//2]
    rechts = sort[len(sort)//2:]


    if zahl <= max(links):
        for i in range(len(links)):
            if i < zahl <= i+1:
                links.insert(i,zahl)
            if zahl < min(links):
                links.insert(0,zahl)

    else:
        for i in range(len(rechts)):
            if i < zahl <= i+1:
                rechts.insert(i,zahl) 
           
                

    sort = links + rechts

    return sort


Das Problem ist jedoch, dass ich in die rechte Liste, also [4,5,6] keine Zahl einfügen kann. Wenn ich z.B. die 5 einfügen möchte, so gibt er mir die Anfangsliste wieder zurück. Habe ich da irgendwo einen Denkfehler? :?
eckhard
User
Beiträge: 33
Registriert: Montag 14. Dezember 2015, 10:06
Wohnort: Karlsruhe

@unplayable: Dass es mit dem Einfügen von 2 gut ging, lag an Deiner Liste [1,2,3,4,5,6].
Versuche mal in die Liste [3,4,5,6,7,8] die 4 einzufügen.

Aber Du vergleichst in deinem Programm einen Laufindex i mit deiner zahl. Was Du aber
wahrscheinlich wolltest, war den Inhalt von links (bzw. rechts) also links mit zahl zu vergleichen.

Eckhard
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@unplayable: für binäres Einfügen, oder Suchen, gibt es schon das Modul bisect. Das was Du geschrieben hast, hat aber nichts mit binärer Suche zu tun. Lies Dir am besten die Wikipediaseite dazu durch.
Unplayable
User
Beiträge: 51
Registriert: Mittwoch 24. Februar 2016, 22:09

Oh mist ja. War ein Denkfehler von mir.

@ Sirius: Ich muss es aber selbst schreiben :)
__deets__
User
Beiträge: 14494
Registriert: Mittwoch 14. Oktober 2015, 14:29

Durch die teillisten die du erzeugst, sowie das Zusammensetzen eben jener Listen tut dein Algorithmus sehr, sehr viel mehr als er sollte. Du darfst nur mit Indizes arbeiten, und am besten rekursiv, so das nur ganz am Ende eine einfüge Operation steht.
Antworten