Binärsuche (sortierte Liste)

[johnny223]

Hallo zusammen,

ich habe eine Frage zu folgender Aufgabe (siehe Anhang/Link). Link: https://ibb.co/ZJ4nLcD

Kann mir einer eventuell bestätigen ob dieser Code richtig ist?

Danke!

Code: Alles auswählen

def countOnes(l):
    i = len(l) // 2
    i_vorher = -1

    schrittgroesse = i // 2
    while i - i_vorher != 0:
        print("s: " + str(i))
        elem = l[i]

        if elem == 1:
            break;

        i_vorher = i
        i += schrittgroesse
        schrittgroesse //= 2

    while i >= 0 and l[i] == 1:
        i -= 1
    i += 1

    if i < 0 or i >= len(l) or l[i] == 0:
        return 0
    else:
        return len(l) - i

l = [0,0,0,0,1,1,1,1]
print(countOnes(l))

[einfachTobi]

Da hast du wohl deine Hausaufgaben durcheinander gebracht. Der Link zeigt eine nicht zum Code passende Aufgabe. Auf Facebook hat dir aber schon jemand einige Hinweise gegeben. Warum hältst du es für klug uns den Code ohne Berücksichtigung der Hinweise hinzuwerfen? Du kannst selbst ganz einfach prüfen, ob er funktioniert, wie er soll: Du musst als Ergebnis eine 4 erhalten, wenn Einsen gezählt werden sollen. Gib einen anderen Input hinein, bspw: [0, 1, 0, 0, 1]. Ist das Ergebnis 2? Dann ists wohl korrekt. Wobei ich die Aufgabenstellung nicht mehr ganz im Kopf habe.

[Sirius3]

Funktionen schreibt man wie Variablennamen nach Konvention komplett klein.
Variablennamen müssen aussagekäftig sein, einbuchstabige Namen sind das nicht, und l hat zusätzlich noch das Problem, dass man es als 1 oder I lesen kann.
Wenn man Variablen einen Dummy-Wert zuweisen muß, damit eine while-Schleife losläuft, dann hat man eigentlich eine Schleife, bei der die Bedingung am Ende per if am Ende geprüft wird. Strings setzt man nicht per + zusammen, sondern nutzt Formatstrings.
; ist überflüssig.
i kann niemals kleiner 0 werden.
Kommen wir also bei diesem Code raus:

Code: Alles auswählen

def count_ones(numbers):
    i = len(numbers) // 2
    schrittgroesse = i // 2
    while True:
        print(f"s: {i}")
        elem = numbers[i]
        if elem == 1:
            break

        i_vorher = i
        i += schrittgroesse
        schrittgroesse //= 2
        if i == i_vorher:
            break
    
    while i >= 0 and numbers[i] == 1:
        i -= 1
    i += 1

    if i >= len(numbers) or numbers[i] == 0:
        return 0
    else:
        return len(numbers) - i

Das i_vorher kann man auch einfach eliminieren, da das ja direkt mit der Schrittgroesse korrelliert:

Code: Alles auswählen

def count_ones(numbers):
    i = len(numbers) // 2
    schrittgroesse = i
    while schrittgroesse != 0:
        schrittgroesse //= 2
        print(f"s: {i}")
        elem = numbers[i]
        if elem == 1:
            break
        i += schrittgroesse
    
    while i >= 0 and numbers[i] == 1:
        i -= 1
    i += 1

    if i < 0 or i >= len(l) or l[i] == 0:
        return 0
    else:
        return len(l) - i

Der Code ist sehr ineffizient, wenn Du mehr als die Hälfte 1en in Deiner Liste hast.
Und der Code ist falsch, wenn die Länge der Liste nicht gerade eine Zweierpotenz ist.