Wyszukiwanie binarne w liście posortowanej

Wyszukiwanie liniowe i binarne - Algorytmy z podstawy programowej (Python)

Gdy lista jest **posortowana**, można szukać dużo szybciej: patrzymy na środkowy element i odrzucamy połowę, w której szukanego na pewno nie ma. Po każdym kroku przedział maleje o połowę, więc w liście miliona elementów wystarczy około 20 porównań. Krokuj i obserwuj zmienne `lewy`, `prawy` i `srodek`.

dane = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
x = 23
lewy = 0
prawy = len(dane) - 1
while lewy <= prawy:
    srodek = (lewy + prawy) // 2
    print(lewy, prawy, "środek:", dane[srodek])
    if dane[srodek] == x:
        print("znaleziono na pozycji", srodek)
        break
    elif dane[srodek] < x:
        lewy = srodek + 1
    else:
        prawy = srodek - 1
else:
    print("brak")

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

Wszystkie lekcje kursu Algorytmy z podstawy programowej·Zaloguj się, aby zapisać postęp na koncie.