Wyszukiwanie binarne w Pythonie

powrót

Algorytm wyszukiwania binarnego, wykorzystujący technikę "dziel i zwyciężaj", jest skutecznym algorytmem służący do znajdowania określonego elementu w posortowanym zbiorze danych. Polega on na podziale tego zbioru na pół i porównywaniu poszukiwanego elementu z elementem w środku zbioru. Na podstawie wyniku tego porównania algorytm decyduje, czy poszukiwany element znajduje się w lewej czy prawej części zbioru i powtarza ten proces na odpowiedniej połowie zbioru. Wyszukiwanie binarne jest wydajne, ponieważ po każdej iteracji eliminuje połowę zbioru jako potencjalne miejsce, w którym znajduje się poszukiwany element.

Kroki działania algorytmu wyszukiwania binarnego

Przeanalizujmy przykład:$$1\ 2\ 4\ 7\ 8\ 9\ 11$$wyszukując liczbę 8.

1. Wybierz element środkowy zbioru: $$1\ 2\ 4\ ->\ 7\ <-\ 8\ 9\ 11$$
2. Porównaj go z poszukiwanym elementem: czy 7 jest szukaną wartością, czyli 8?
3. Jeśli znaleziono poszukiwany element, zakończ algorytm.
4. Jeśli poszukiwany element jest mniejszy niż element środkowy, kontynuuj wyszukiwanie w lewej połowie zbioru, pomijając prawą połowę oraz element środkowy. W naszym przykładzie ten przypadek nie zachodzi.
5. Jeśli poszukiwany element jest większy niż element środkowy, kontynuuj wyszukiwanie w prawej połowie zbioru, pomijając lewą połowę oraz element środkowy. Pozostaje nam zbiór złożony z elementów: $$8\ 9\ 11$$
6. Wybierz element środkowy zbioru: $$8\ ->\ 9\ <-\ 11$$
7. Porównaj go z poszukiwanym elementem: czy 9 jest szukaną wartością, czyli 8?
8. Jeśli znaleziono poszukiwany element, zakończ algorytm.
9. Jeśli poszukiwany element jest mniejszy niż element środkowy, kontynuuj wyszukiwanie w lewej połowie zbioru, pomijając prawą połowę oraz element środkowy.Pozostaje nam zbiór złożony z jednego elementu: $$8$$
10. Jeśli poszukiwany element jest większy niż element środkowy, kontynuuj wyszukiwanie w prawej połowie zbioru, pomijając lewą połowę oraz element środkowy. W naszym przykładzie ten przypadek nie zachodzi.
11. Algorytm kończymy, gdy znajdziemy szukany element lub, gdy nie znajdziemy i zbiór jest jednoelementowy.

Wyszukiwanie binarne jest znacznie bardziej efektywne niż liniowe przeszukiwanie, które wymagałoby sprawdzenia każdego elementu w zbiorze. Jego złożoność obliczeniowa wynosi $$O(log n)$$, gdzie "n" to liczba elementów w zbiorze. Jest to więc szybki sposób na odnalezienie elementu w dużych, posortowanych zbiorach danych.

Zadanie

Dla zadanego zbioru n uporządkowanych niemalejąco liczb całkowitych określ, na której pozycji znajduje się liczba szukana s. Jeśli liczba nie występuje w zbiorze, to zwróć -1. Elementy zbioru numerujemy od 0 do n - 1.

Rozwiązanie iteracyjne:

#****************algorytm.edu.pl**************
def binary_search(zbior, s): # zbiór - uporządkowany zbiór liczb, s - wartość szukana
    l = 0 # indeks pierwszego elementu w zbiorze
    p = len(zbior) - 1 # indeks ostatniego elementu w zbiorze
    while l <= p:
        sr = (l + p)//2 # wyznaczamy indeks środkowego elementu zbioru
        if s == zbior[sr]: # jeśli znaleźliśmy szukaną wartość
            return sr
        if s < zbior[sr]: # jeśli szukana wartość jest mniejsza od elementu środkowego
            p = sr - 1 # to ograniczamy przeszukiwanie do zbioru dla indeksów z przedziału [l, sr - 1]
        else: # w przeciwnym razie
            l = sr + 1 # ograniczamy przeszukiwanie do zbioru dla indeksów z przedziału [sr + 1, p]
    return -1 # jeśli nie znaleziono szukanej wartości

#************główna część programu*****************

zbior = [1, 2, 5, 7, 9, 12, 14, 19] # uporządkowany zbiór liczb
s = 9
if binary_search(zbior, s) == -1:
    print("nie znaleziono liczby", s)
else:
    print("Liczba", s, "znajduje się pod indeksem", binary_search(zbior, s))

Wyjście

Liczba 9 znajduje się pod indeksem 4

Rozwiązanie rekurencyjne:

#****************algorytm.edu.pl**************
def binary_search(zbior, s, l, p): # zbiór - uporządkowany zbiór liczb, s - wartość szukana,
                                    # l - lewy indeks podtablicy, p - prawy indeks podtablicy
    if l >p: return -1 # jeśli nie znaleziono szukanej wartości
    sr = (l + p)//2 # wyznaczamy indeks środkowego elementu zbioru
    if s == zbior[sr]: # jeśli znaleźliśmy szukaną wartość
        return sr
    if s < zbior[sr]: # jeśli szukana wartość jest mniejsza od elementu środkowego
        return binary_search(zbior, s, l, sr - 1) # to ograniczamy przeszukiwanie do zbioru dla indeksów z przedziału [l, sr - 1]
    else: # w przeciwnym razie
        return binary_search(zbior, s, sr + 1, p) # to ograniczamy przeszukiwanie do zbioru dla indeksów z przedziału [sr + 1, p]

#************główna część programu*****************

zbior = [1, 2, 5, 7, 9, 12, 14, 19] # uporządkowany zbiór liczb
s = 9
if binary_search(zbior, s, 0, len(zbior) - 1) == -1:
    print("nie znaleziono liczby", s)
else:
    print("Liczba", s, "znajduje się pod indeksem", binary_search(zbior, s, 0, len(zbior) - 1))