Pierwsze miejsce nie mniejsze od x

Powtórzenie: wyszukiwanie binarne i metoda połowienia - Informatyka - liceum klasa 4, zakres rozszerzony (Python)

Przypomnienie: w liście posortowanej wyszukiwanie binarne trzyma przedział `[left, right)`, w którym jest szukane miejsce, i co krok sprawdza środek. Wersja "pierwsze miejsce z wartością co najmniej `x`" działa też, gdy `x` nie ma w liście albo występuje wiele razy.

def lower_bound(a, x):
    left, right = 0, len(a)
    while left < right:
        middle = (left + right) // 2
        if a[middle] < x:
            left = middle + 1
        else:
            right = middle
    return left

a = [2, 4, 4, 4, 7, 9]
print(lower_bound(a, 4), lower_bound(a, 5), lower_bound(a, 1), lower_bound(a, 10))

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Informatyka - liceum klasa 4, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.