Algorytm wyszukiwania binarnego w Pythonie

Przeszukuj posortowane listy w logarytmicznym czasie O(log n). Uruchom i zrozum wyszukiwanie binarne w Pythonie, w tym logikę krok po kroku, przypadki brzegowe i optymalizacje.

Spróbuj w Edytorze

Przegląd

Wyszukiwanie binarne to wyjątkowo skuteczny algorytm znajdowania elementu na posortowanej liście. W przeciwieństwie do wyszukiwania liniowego, które skanuje każdy element sekwencyjnie w czasie O(n), wyszukiwanie binarne polega na wielokrotnym dzieleniu interwału wyszukiwania na pół.

Wyszukiwanie rozpoczyna się od sprawdzenia środkowego elementu tablicy. Jeśli wartość docelowa pasuje do środkowego elementu, zwracana jest jej pozycja. Jeśli cel jest mniejszy, algorytm zawęża poszukiwania do dolnej połowy; jeśli cel jest większy, zawęża go do górnej połowy. Proces ten powtarza się do momentu znalezienia elementu lub do momentu, gdy rozmiar podtablicy spadnie do zera.

Aby zaimplementować wyszukiwanie binarne w Pythonie, używamy dwóch wskaźników (dolny i wysoki) do śledzenia aktywnych granic wyszukiwania. Ponieważ przestrzeń poszukiwań zmniejsza się o połowę na każdym kroku, algorytm jest wykonywany w czasie O(log n), co czyni go idealnym rozwiązaniem w przypadku ogromnych baz danych.

Dane wyjściowe kodu i wykonania

Standardowa iteracyjna implementacja wyszukiwania binarnego, która zwraca indeks elementu docelowego na posortowanej liście.

binary_search.py

Spróbuj w Edytorze

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]
        
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
            
    return -1

# Sorted test dataset
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_val = 23

index = binary_search(data, target_val)
print(f"Dataset: {data}")
print(f"Target: {target_val}")
if index != -1:
    print(f"Target found at index: {index}")
else:
    print("Target not found in dataset")

Wyjście terminala

Dataset: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target: 23
Target found at index: 5

Wdrażanie krok po kroku

Indeksowanie zapytań i przeszukiwanie tabel bazy danych
Znajdowanie wartości progowych lub granicznych w ciągłych zakresach matematycznych
Funkcje autouzupełniania i wyszukiwania w polach tekstowych

Często zadawane pytania

Czy lista musi być posortowana, aby wyszukiwanie binarne działało?

Tak, wyszukiwanie binarne ściśle opiera się na sortowaniu elementów. Jeśli lista nie jest posortowana, logika porównania załamuje się i należy najpierw posortować listę lub zastosować wyszukiwanie liniowe.

Dlaczego warto używać iteracyjnego wyszukiwania binarnego zamiast rekurencyjnego wyszukiwania binarnego?

Chociaż rekurencyjne wyszukiwanie binarne jest eleganckie, w środowisku produkcyjnym często preferowane jest iteracyjne wyszukiwanie binarne. Podejście iteracyjne działa w przestrzeni pomocniczej O(1), podczas gdy wyszukiwanie rekurencyjne zajmuje przestrzeń O(log n) ze względu na stos wywołań, ryzykując przepełnienie stosu w przypadku bardzo dużych danych wejściowych.

Powiązane tematy

Algorytmy sortowania w Pythonie

Poznaj algorytmy sortowania w Pythonie. Wizualizuj sortowanie bąbelkowe i sortowanie przez scalanie natywnie w kontekście IDE przeglądarki.

Samouczek algorytmu sortowania przez scalanie w Pythonie

Dowiedz się, jak zaimplementować sortowanie przez scalanie w Pythonie. Interaktywny przykład strategii sortowania „Dziel i zwyciężaj” krok po kroku.

Przewodnik po algorytmie szybkiego sortowania w języku Python

Poznaj algorytm szybkiego sortowania w Pythonie. Naucz się selekcji przestawnej, partycjonowania i rekurencji w tym interaktywnym przykładzie kodowania.