Wyszukiwanie binarne na maturę (Binary Search) - Szukaj w ułamku sekundy (Python i C++)

Wyobraź sobie, że musisz znaleźć konkretne słowo w grubym słowniku języka polskiego. Czy czytasz go strona po stronie, od deski do deski? Oczywiście, że nie! Otwierasz go w połowie, sprawdzasz literę i jeśli Twoje słowo jest alfabetycznie dalej – odrzucasz całą lewą połowę książki i szukasz tylko w prawej. Na tym właśnie polega wyszukiwanie binarne (ang. binary search).

Na maturze z informatyki bardzo często pracujemy na ogromnych zbiorach danych. Algorytm wyszukiwania binarnego to absolutny "must-have", który pozwala drastycznie przyspieszyć działanie programu i zmieścić się w wyznaczonym limicie czasu.

Kluczowy warunek: Tablica MUSI być posortowana!

Dlaczego Binary Search jest tak szybki?

Zwykłe przeglądanie tablicy element po elemencie to tzw. wyszukiwanie liniowe. Jego złożoność to O(n), co oznacza, że dla tablicy o rozmiarze 1 000 000 elementów, w najgorszym razie musisz wykonać 1 000 000 sprawdzeń.

Wyszukiwanie binarne działa w oparciu o technikę "dziel i zwyciężaj". Złożoność tego algorytmu to O(log n). Oznacza to, że za każdym krokiem odrzucamy połowę elementów. Dla tablicy 1 000 000-elementowej znalezienie wyniku zajmie nam w najgorszym pesymistycznym przypadku... zaledwie około 20 kroków! Przeskok w wydajności jest gigantyczny.

Algorytm krok po kroku na żywym organizmie

Przeanalizujmy zbiór 8 uporządkowanych liczb: [1, 2, 5, 8, 9, 11, 15, 20]. Szukamy liczby 11. Potrzebujemy trzech zmiennych (wskaźników na indeksy):

• L (lewy kraniec obszaru poszukiwań)
• P (prawy kraniec obszaru poszukiwań)
• S (środek, obliczany jako (L+P)//2)

Symulacja działania:

1. Krok 1: L = 0, P = 7. Środek S = (0+7)//2 = 3. Pod indeksem 3 znajduje się liczba 8. Szukane 11 jest większe od 8, więc odrzucamy lewą połowę. Nowy lewy kraniec: L = S + 1 = 4.
2. Krok 2: Teraz szukamy w przedziale od indeksu 4 do 7. L = 4, P = 7. Środek S = (4+7)//2 = 5. Pod indeksem 5 znajduje się liczba 11. Znaleźliśmy! Koniec algorytmu.

Jeśli w pewnym momencie wskaźnik lewy minie się z prawym (L > P), oznacza to, że przeszukaliśmy wszystko i elementu po prostu nie ma w tablicy.

Implementacja - Gotowy Kod (Zgodnie z dobrymi praktykami)

Kod algorytmu najlepiej zamknąć w osobnej funkcji i umieścić ją na samej górze pliku. Istnieją dwie wersje: iteracyjna (na pętli while) i rekurencyjna. Wersja iteracyjna jest znacznie bezpieczniejsza na maturze, ponieważ nie grozi przepełnieniem stosu (Stack Overflow).

Python - Wersja iteracyjna (Zalecana)

def szukaj_binarnie(tablica, szukana):
    l = 0
    p = len(tablica) - 1
    
    while l <= p:
        s = (l + p) // 2  # dzielenie całkowite
        
        if tablica[s] == szukana:
            return s      # Znaleziono, zwracamy indeks
            
        if tablica[s] < szukana:
            l = s + 1     # Szukamy w prawej połowie
        else:
            p = s - 1     # Szukamy w lewej połowie
            
    return -1             # Zwracamy -1, jeśli elementu nie ma

# Przykład użycia (część główna programu)
tab = [1, 2, 5, 8, 9, 11, 15, 20]
element = 11
pozycja = szukaj_binarnie(tab, element)

if pozycja != -1:
    print(f"Znaleziono na indeksie: {pozycja}")
else:
    print("Nie znaleziono.")

C++ - Wersja iteracyjna (Zalecana)

#include <iostream>
#include <vector>
using namespace std;

int szukaj_binarnie(const vector<int>& tab, int szukana) {
    int l = 0;
    int p = tab.size() - 1;
    
    while(l <= p) {
        int s = (l + p) / 2;
        
        if(tab[s] == szukana) {
            return s;
        }
        
        if(tab[s] < szukana) {
            l = s + 1;
        } else {
            p = s - 1;
        }
    }
    return -1;
}

int main() {
    vector<int> tab = {1, 2, 5, 8, 9, 11, 15, 20};
    int element = 11;
    
    int pozycja = szukaj_binarnie(tab, element);
    
    if(pozycja != -1) {
        cout << "Znaleziono na indeksie: " << pozycja << endl;
    } else {
        cout << "Nie znaleziono." << endl;
    }
    return 0;
}

C++ - Wersja rekurencyjna

int szukaj_rekurencyjnie(const vector<int>& tab, int l, int p, int szukana) {
    if (l > p) {
        return -1;
    }
    
    int s = (l + p) / 2;
    
    if (tab[s] == szukana) return s;
    
    if (tab[s] < szukana) {
        return szukaj_rekurencyjnie(tab, s + 1, p, szukana);
    } else {
        return szukaj_rekurencyjnie(tab, l, s - 1, szukana);
    }
}

Gdzie wykorzystasz to na maturze?

• Szybkie sprawdzanie obecności: Jeśli w zadaniu musisz odpowiedzieć, ile liczb z pliku A występuje również w ogromnym pliku B (wcześniej musisz posortować plik B).
• Bisekcja (Miejsce zerowe funkcji): Mechanizm wyszukiwania binarnego to fundament algorytmu poszukiwania miejsca zerowego metodą połowienia przedziałów! Zamiast indeksów w tablicy, operujemy tam na współrzędnych x rzeczywistych.
• Zgadywanie wyniku: Czasem rozwiązaniem zadania jest znalezienie optymalnej, najmniejszej lub największej wartości, która spełnia dany warunek. Używamy wtedy tzw. "wyszukiwania binarnego po wyniku".

Typowe pułapki (Na co uważać!)

Podsumowanie

Wyszukiwanie binarne to potężne, ale bardzo proste narzędzie. Zapamiętaj podstawowy wzorzec: policz środek -> sprawdź z szukaną -> zacieśnij granice. Wyćwicz napisanie tego algorytmu z pamięci tak, aby zajmowało Ci to mniej niż 2 minuty. To pewny punkt w maturalnym arsenale.

Chcesz więcej trików algorytmicznych? Sprawdź nasz kurs do matury z informatyki.