Algorytm wyszukiwania binarnego

Wyszukiwanie binarne (połowienie) to jeden z najważniejszych algorytmów wyszukiwania omawianych na maturze rozszerzonej z informatyki — klasyczny przykład, jak sprytne wykorzystanie właściwości danych (posortowania) pozwala drastycznie przyspieszyć operację w porównaniu do naiwnego podejścia.

Podstawowym warunkiem wstępnym algorytmu jest to, że tablica musi być posortowana (niemalejąco lub nierosnąco). Zasada działania polega na dzieleniu przedziału poszukiwań na pół i porównywaniu szukanej wartości z elementem znajdującym się w środkowym indeksie. Jeśli szukana wartość jest mniejsza od elementu środkowego, poszukiwania kontynuowane są w lewej połowie tablicy; jeśli większa — w prawej. Proces powtarza się, aż element zostanie znaleziony lub zakres poszukiwań stanie się pusty.

Materiał szczegółowo omawia obliczanie indeksu środkowego jako $\lfloor \frac{lewy + prawy}{2} \rfloor$ oraz analizuje złożoność obliczeniową algorytmu — $O(\log n)$ — co czyni go znacznie bardziej efektywnym niż wyszukiwanie liniowe ($O(n)$) dla dużych zbiorów danych. Uczeń poznaje kluczową własność logarytmicznego wzrostu: podwojenie rozmiaru tablicy zwiększa liczbę kroków algorytmu jedynie o jeden, co jest fundamentalną cechą odróżniającą złożoność logarytmiczną od liniowej.

Ważnym tematem jest też wyjaśnienie, dlaczego wyszukiwanie binarne nie jest stosowane w listach wiązanych (linked lists) — algorytm wymaga dostępu swobodnego (random access) do dowolnego elementu w czasie $O(1)$, którego listy wiązane nie zapewniają (dostęp do $i$-tego elementu zajmuje tam $O(n)$).

Materiał obejmuje obie możliwe implementacje algorytmu — iteracyjną i rekurencyjną — oraz podkreśla, że wyszukiwanie binarne nie wymaga dodatkowej pamięci proporcjonalnej do rozmiaru danych ($O(1)$ pamięci dodatkowej). Uczeń ćwiczy też praktyczne obliczenia — na przykład wyznaczanie indeksu środkowego dla konkretnego zakresu indeksów.

Ten zestaw pytań i fiszek buduje pełne zrozumienie mechaniki, warunków stosowalności oraz analizy złożoności wyszukiwania binarnego — temat regularnie pojawiający się w zadaniach maturalnych z informatyki.

• Uczeń zna podstawowy warunek wstępny wyszukiwania binarnego — posortowanie danych
• Uczeń opisuje mechanikę dzielenia przedziału poszukiwań na połowę w każdym kroku
• Uczeń oblicza indeks środkowy przedziału dla podanych granic
• Uczeń zna złożoność obliczeniową O(log n) i rozumie jej wpływ na wydajność przy dużych zbiorach danych
• Uczeń wyjaśnia, dlaczego wyszukiwanie binarne nie działa efektywnie na listach wiązanych
• Uczeń rozróżnia implementację iteracyjną i rekurencyjną algorytmu
• Uczeń porównuje wyszukiwanie binarne z liniowym pod względem wymagań wstępnych i wydajności

Materiał tematyczny (bez dokumentu źródłowego): algorytm wyszukiwania binarnego (połowienia) w tablicy posortowanej — zasada działania, wymóg posortowania danych, liczba kroków potrzebnych do znalezienia elementu, złożoność obliczeniowa logarytmiczna, zgodnie z zakresem matury rozszerzonej z informatyki.