Wyszukiwanie binarne

2.1 Definicja wyszukiwania binarnego i jego główne koncepcje

Wyszukiwanie binarne — to algorytm wyszukiwania elementu w posortowanej tablicy, który działa na zasadzie podziału tablicy na połowy. Ten algorytm jest znacznie bardziej efektywny niż wyszukiwanie liniowe dla dużych tablic, ponieważ zmniejsza liczbę sprawdzeń poprzez podział tablicy na dwie części w każdej iteracji.

Główne koncepcje:

• Posortowana tablica: Wyszukiwanie binarne działa tylko na posortowanych tablicach.
• Podział na połowy: Algorytm porównuje poszukiwany element z elementem w środku tablicy.
• Podział rekurencyjny lub iteracyjny: Jeśli poszukiwany element jest mniejszy od średniego, wyszukiwanie kontynuuje się w lewej połowie tablicy, w przeciwnym razie — w prawej.
• Warunek zakończenia: Wyszukiwanie kończy się, gdy element zostanie znaleziony lub zakres wyszukiwania staje się pusty.

Ważne! Do wyszukiwania binarnego potrzebna jest posortowana tablica.

Aby wyszukiwanie binarne działało poprawnie, dane wejściowe muszą być posortowane rosnąco. Jest to podstawowy i jedyny warunek, ponieważ algorytm opiera się na fakcie, że elementy tablicy są uporządkowane. Dzięki temu może on efektywnie wykluczać połowę elementów na każdym kroku wyszukiwania.

Przykład posortowanej tablicy:

sorted_array = [1, 3, 5, 7, 9, 11, 13]

2.2 Krok po kroku realizacja wyszukiwania binarnego

Zasada działania wyszukiwania binarnego:

1. Inicjalizacja: Ustawić początkowe granice wyszukiwania (lewa i prawa granica tablicy).
2. Wybór środkowego elementu: Znaleźć indeks środkowego elementu tablicy.
3. Porównanie: Porównać środkowy element z poszukiwaną wartością.
4. Aktualizacja granic:
   1. Jeśli środkowy element jest równy poszukiwanej wartości, zwrócić jego indeks.
   2. Jeśli poszukiwana wartość jest mniejsza od środkowego elementu, zaktualizować prawą granicę wyszukiwania.
   3. Jeśli większa — zaktualizować lewą granicę.
5. Powtórzenie: Powtarzać kroki 2-4 do znalezienia elementu lub aż lewa granica stanie się większa od prawej.

Krok po kroku algorytm:

1. Inicjalizacja: Ustawić left na 0 i right na len(arr) - 1.
2. Obliczyć środkowy element: mid = (left + right) // 2
3. Porównać z docelowym elementem:
   1. Jeśli arr[mid] == target, zwrócić mid
   2. Jeśli arr[mid] < target, zaktualizować left = mid + 1
   3. Jeśli arr[mid] > target, zaktualizować right = mid - 1
4. Powtórzenie: Wrócić do kroku 2 aż left <= right
5. Jeśli element nie zostanie znaleziony: Zwrócić -1

Iteracyjna realizacja wyszukiwania binarnego w Pythonie:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Przykład użycia:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Element {target} znaleziony na indeksie {result}")  # Wynik: Element 7 znaleziony na indeksie 3

2.3 Złożoność czasowa wyszukiwania binarnego O(log n)

Wyszukiwanie binarne ma złożoność czasową O(log n), gdzie n — to liczba elementów w tablicy. Oznacza to, że na każdym kroku algorytm dzieli liczbę elementów na pół, co znacznie przyspiesza wyszukiwanie w porównaniu z wyszukiwaniem liniowym, mającym złożoność czasową O(n).

Analiza złożoności czasowej:

• Najlepszy przypadek (Best case): Element znaleziony na pierwszym kroku, O(1).
• Średni przypadek (Average case): O(log n).
• Najgorszy przypadek (Worst case): Element znaleziony na ostatnim kroku lub nieobecny, O(log n).

Przykład dla analizy złożoności czasowej:

sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
index = binary_search(sorted_array, target)
print(f"Element {target} znaleziony na indeksie {index}")  # Wynik: Element 7 znaleziony na indeksie 3

# Algorytm wykonał 3 kroki (logarytm z 7 elementów) dla znalezienia elementu, 
# co odpowiada O(log n)

Graficzne przedstawienie złożoności:

Wyobraź sobie tablicę z 16 elementami.

Przypuśćmy, że szukamy elementu 15, wtedy kroki będą takie:

Pierwszy krok. Sprawdzi środkowy element (8 elementów pozostaje).

Drugi krok. Sprawdzi środkowy element w pozostałej połowie (4 elementy pozostają).

Trzeci krok. Sprawdzi środkowy element w pozostałej połowie (2 elementy pozostają).

Czwarty krok. Sprawdzi ostatni element (1 element pozostaje).

W rezultacie algorytm wykona 4 kroki dla tablicy z 16 elementami, co odpowiada logarytmowi o podstawie 2 z 16, czyli log2(16) = 4. To właśnie jest złożoność logarytmiczna O(log n).