Wyszukiwanie binarne

ALGORYTM:

def binary_search(searched: int, set_to_search: List[int]):
    start, end = 0, len(set_to_search) - 1
    operations = 0
    
    while start <= end:
        operations += 1
        middle_idx = (start + end) // 2
        
        if searched > set_to_search[middle_idx]:
            start = middle_idx + 1
        
        elif searched < set_to_search[middle_idx]:
            end = middle_idx - 1
            
        else:
            print(f"opperations: {operations}")
            return middle_idx

Jak działa wyszukiwanie binarne?

Wyszukiwanie binarne działa na posortowanej liście. Zamiast sprawdzać każdy element po kolei, za każdym razem wybiera element znajdujący się mniej więcej na środku listy.

Na początku ustawiamy dwie zmienne:

start = 0
end = len(set_to_search) - 1

start wskazuje początek przeszukiwanego zakresu, a end jego koniec. Następnie obliczamy środkowy indeks:

middle_idx = (start + end) // 2

Pod tym indeksem znajduje się wartość, którą porównujemy z liczbą szukaną.

Jeżeli szukana liczba jest większa od środkowego elementu, możemy pominąć całą lewą część listy:

start = middle_idx + 1

Jeżeli jest mniejsza, odrzucamy prawą część:

end = middle_idx - 1

Gdy wartości są równe, funkcja zwraca indeks znalezionego elementu.

Po każdym przebiegu pętli zakres wyszukiwania zmniejsza się mniej więcej o połowę. Dzięki temu nawet przy dużej liczbie elementów algorytm potrzebuje stosunkowo niewielu operacji.

Trzeba pamiętać, że lista musi być wcześniej posortowana. W przeciwnym razie algorytm może odrzucić tę część listy, w której faktycznie znajduje się szukana wartość.

Złożoność czasowa wyszukiwania binarnego wynosi O(log n), dzięki czemu dobrze sprawdza się również przy dużych zbiorach danych.