Połowienie przedziału

Wyszukiwanie binarne w zbiorze uporządkowanym - Informatyka - liceum klasa 1, zakres rozszerzony (Python)

Gdy lista jest **uporządkowana** (rosnąco), można szukać dużo szybciej niż po kolei: porównaj `x` ze środkowym elementem. Jeśli jest mniejszy, `x` może być tylko w lewej połowie, jeśli większy - tylko w prawej. Każdy krok **połowi** przedział, więc dla miliona elementów wystarcza około 20 kroków (`2²⁰ ≈ 10⁶`). Program wypisuje kolejne przedziały `[left, right]`.

A = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
x = 23
left, right = 0, len(A) - 1
while left <= right:
    mid = (left + right) // 2
    print("przedział", left, right, "środek", mid, "=", A[mid])
    if A[mid] == x:
        print("znaleziono na pozycji", mid)
        break
    if A[mid] < x:
        left = mid + 1
    else:
        right = mid - 1
else:
    print("brak")

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

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