# Wyszukiwanie Liniowe (Sekwencyjne) Wyszukiwanie danych to jedna z fundamentalnych operacji w informatyce. Niezależnie od tego, czy szukamy nazwiska w książce telefonicznej, pliku na dysku komputera, czy produktu w bazie danych sklepu internetowego, potrzebujemy efektywnych metod, aby szybko znaleźć pożądane informacje. Istnieją różne algorytmy wyszukiwania, a jednym z najbardziej podstawowych i uniwersalnych jest **wyszukiwanie liniowe** (sekwencyjne). ## Czym jest wyszukiwanie liniowe? Wyszukiwanie liniowe, znane również jako wyszukiwanie sekwencyjne, jest najprostszym algorytmem wyszukiwania. Jego zasada działania polega na przeglądaniu każdego elementu w zbiorze danych po kolei, od początku do końca, aż do momentu znalezienia szukanego elementu lub stwierdzenia, że elementu nie ma w zbiorze. > **Definicja:** **Wyszukiwanie liniowe (sekwencyjne)** to algorytm wyszukiwania, który polega na sukcesywnym sprawdzaniu każdego elementu w zbiorze danych, aż do znalezienia szukanego elementu lub przejścia przez cały zbiór. ### Zaleta danych nieuporządkowanych Jedną z głównych zalet wyszukiwania liniowego jest to, że nie wymaga ono żadnych specjalnych warunków dotyczących uporządkowania danych. Może być stosowane zarówno do posortowanych, jak i nieposortowanych danych, co czyni go bardzo elastycznym narzędziem. ## Jak działa algorytm wyszukiwania liniowego? Logika działania wyszukiwania liniowego jest bardzo intuicyjna i można ją przedstawić w kilku prostych krokach: 1. **Rozpoczęcie:** Algorytm zaczyna przeglądanie od pierwszego elementu w zbiorze danych. 2. **Porównanie:** Bieżący element jest porównywany z wartością, której szukamy. 3. **Sukces:** Jeśli bieżący element jest równy szukanej wartości, algorytm kończy działanie sukcesem i zwraca pozycję (indeks) znalezionego elementu. 4. **Kontynuacja:** Jeśli bieżący element nie jest równy szukanej wartości, algorytm przechodzi do następnego elementu w zbiorze. 5. **Powtarzanie:** Kroki 2-4 są powtarzane, aż do momentu, gdy wszystkie elementy zostaną sprawdzone lub element zostanie znaleziony. 6. **Porażka:** Jeśli wszystkie elementy zostały sprawdzone, a szukana wartość nie została znaleziona, algorytm kończy działanie niepowodzeniem i zwraca informację o braku elementu (często jest to specjalna wartość, np. $ -1 $). ### Przykład działania Załóżmy, że mamy tablicę liczb: $ [15, 8, 23, 4, 42, 10] $ i szukamy liczby $ 42 $. 1. Porównujemy $ 15 $ z $ 42 $. Nie są równe. 2. Porównujemy $ 8 $ z $ 42 $. Nie są równe. 3. Porównujemy $ 23 $ z $ 42 $. Nie są równe. 4. Porównujemy $ 4 $ z $ 42 $. Nie są równe. 5. Porównujemy $ 42 $ z $ 42 $. Są równe! Algorytm zwraca indeks $ 4 $ (zakładając indeksowanie od $ 0 $). Jeśli szukalibyśmy liczby $ 99 $ w tej samej tablicy, algorytm przeszedłby przez wszystkie elementy i dopiero po sprawdzeniu $ 10 $ stwierdziłby, że $ 99 $ nie ma w zbiorze. ## Wydajność i złożoność obliczeniowa **Złożoność obliczeniowa** opisuje, jak czas wykonania algorytmu rośnie wraz ze wzrostem rozmiaru danych wejściowych. Jest to kluczowy parametr oceny efektywności algorytmu. > **Definicja:** **Złożoność obliczeniowa** to miara ilości zasobów (np. czasu lub pamięci) potrzebnych algorytmowi do wykonania zadania w zależności od rozmiaru danych wejściowych. ### Najgorszy, najlepszy i średni przypadek Dla wyszukiwania liniowego: * **Najlepszy przypadek:** Szukany element jest pierwszym elementem w zbiorze. Wymaga to tylko jednego porównania. Czas wykonania jest stały, niezależny od rozmiaru zbioru. * **Najgorszy przypadek:** Szukany element jest ostatnim elementem w zbiorze lub nie ma go wcale. Algorytm musi sprawdzić wszystkie $ n $ elementów w zbiorze. * **Średni przypadek:** Szukany element znajduje się mniej więcej w połowie zbioru. Algorytm wykonuje około $ n/2 $ porównań. ### Notacja Big O W notacji Big O, która koncentruje się na zachowaniu algorytmu dla dużych $ n $, wyszukiwanie liniowe ma złożoność **O(n)**. Oznacza to, że czas wy