Algorytm wyszukiwania liniowego

Wyszukiwanie liniowe (ang. linear search) to najprostszy algorytm przeszukiwania danych — punkt wyjścia do dalszej nauki bardziej zaawansowanych technik, takich jak wyszukiwanie binarne. Na maturze rozszerzonej z informatyki uczeń musi rozumieć zarówno mechanikę tego algorytmu, jak i jego ograniczenia w porównaniu z metodami wymagającymi wcześniejszego posortowania danych.

Zasada działania jest intuicyjna: algorytm sprawdza kolejno każdy element tablicy, począwszy od pierwszego, aż do znalezienia szukanej wartości lub osiągnięcia końca tablicy. Kluczową zaletą tego podejścia jest to, że działa ono na dowolnych danych — również na tablicach nieposortowanych — w przeciwieństwie do wyszukiwania binarnego, które wymaga wcześniejszego uporządkowania elementów.

Lekcja szczegółowo analizuje liczbę porównań w różnych scenariuszach: w najlepszym przypadku (szukany element znajduje się na pierwszej pozycji) wystarczy jedno porównanie, natomiast w najgorszym przypadku — gdy elementu nie ma w tablicy lub znajduje się on na samym końcu — algorytm musi wykonać dokładnie $n$ porównań, gdzie $n$ to liczba elementów. Uczeń poznaje też wzór na średnią liczbę porównań przy założeniu, że szukany element rzeczywiście znajduje się w tablicy: $\frac{n+1}{2}$.

Materiał omawia złożoność obliczeniową algorytmu — $O(n)$ w notacji dużego O — oraz porównuje ją bezpośrednio ze złożonością logarytmiczną wyszukiwania binarnego ($O(\log n)$). Uczeń uczy się rozpoznawać, kiedy wyszukiwanie liniowe staje się nieefektywne: przy bardzo dużych zbiorach danych przeszukiwanych wielokrotnie, gdzie koszt liniowego czasu znacząco przewyższa koszt jednorazowego posortowania danych i zastosowania szybszej metody.

Zadania obejmują też praktyczne aspekty implementacji — na przykład zachowanie algorytmu, gdy szukana wartość występuje w tablicy wielokrotnie (standardowo zwracany jest indeks pierwszego napotkanego wystąpienia), oraz konkretne obliczenia liczby porównań dla podanej wielkości tablicy.

Ten zestaw pytań i fiszek buduje solidne podstawy rozumienia kompromisów między prostotą implementacji a wydajnością — fundamentalny temat teorii algorytmów na egzaminie maturalnym.

• Uczeń opisuje zasadę działania algorytmu wyszukiwania liniowego
• Uczeń oblicza liczbę porównań w najlepszym, najgorszym i średnim przypadku
• Uczeń rozumie, że wyszukiwanie liniowe nie wymaga posortowanych danych, w przeciwieństwie do binarnego
• Uczeń zna złożoność czasową O(n) tego algorytmu
• Uczeń rozpoznaje sytuacje, w których wyszukiwanie liniowe staje się nieefektywne dla dużych zbiorów danych
• Uczeń wie, jak algorytm zachowuje się przy wielokrotnym wystąpieniu szukanej wartości
• Uczeń porównuje wyszukiwanie liniowe z wyszukiwaniem binarnym pod względem wymagań i złożoności

Materiał tematyczny (bez dokumentu źródłowego): algorytm wyszukiwania liniowego w tablicy — zasada działania, liczba porównań w najlepszym i najgorszym przypadku, zastosowanie do tablic nieposortowanych, złożoność obliczeniowa, zgodnie z zakresem matury rozszerzonej z informatyki.