Wyszukiwanie liniowe

1. Czym jest wyszukiwanie liniowe?

Wyszukiwanie liniowe (linear search, sequential search) to najprostszy algorytm wyszukiwania elementu w liście.

Idea:

Sprawdź każdy element po kolei, aż znajdziesz szukany lub dojdziesz do końca.

Wizualizacja:

Szukamy: 22

[64, 25, 12, 22, 11, 90]
 ↓
 64 ≠ 22, idź dalej

[64, 25, 12, 22, 11, 90]
     ↓
     25 ≠ 22, idź dalej

[64, 25, 12, 22, 11, 90]
         ↓
         12 ≠ 22, idź dalej

[64, 25, 12, 22, 11, 90]
             ↓
             22 = 22, ZNALEZIONO! Indeks: 3

2. Implementacja podstawowa

3. Implementacja Pythonowa

Uwaga: Wbudowane list.index() używa wyszukiwania liniowego!

4. Wizualizacja z debugiem

Wynik:

Szukam: 22
Lista: [64, 25, 12, 22, 11, 90]

Krok 1: Sprawdzam arr[0] = 64
   64 ≠ 22, idź dalej
Krok 2: Sprawdzam arr[1] = 25
   25 ≠ 22, idź dalej
Krok 3: Sprawdzam arr[2] = 12
   12 ≠ 22, idź dalej
Krok 4: Sprawdzam arr[3] = 22
✅ ZNALEZIONO na indeksie 3!

5. Złożoność czasowa

Najlepszy przypadek: O(1)

Element na pierwszej pozycji:

Najgorszy przypadek: O(n)

Element nie istnieje lub jest na końcu:

Średni przypadek: O(n)

Element w losowym miejscu – średnio n/2 porównań:

6. Złożoność pamięciowa: O(1)

Wyszukiwanie liniowe nie wymaga dodatkowej pamięci.

7. Wyszukiwanie wszystkich wystąpień

Pythonowy sposób:

8. Wyszukiwanie z warunkiem (predykatem)

9. Sentinel Linear Search (optymalizacja)

Dodaj wartownika (sentinel) na końcu, aby uniknąć sprawdzania granicy tablicy:

Zaleta: Jedna operacja mniej w pętli (nie sprawdzamy i < n).

Wada: Modyfikuje tablicę (przywraca potem).

10. Wyszukiwanie w liście posortowanej

Dla posortowanej listy można wcześnie zatrzymać:

Zaleta: Średnio szybsze dla nieistniejących elementów.

Uwaga: Dla posortowanych lepiej użyć wyszukiwania binarnego O(log n)!

11. Wyszukiwanie w strukturach złożonych

11.1. Lista obiektów

11.2. Lista słowników

12. Porównanie z wyszukiwaniem binarnym

Aspekt Wyszukiwanie liniowe Wyszukiwanie binarne
Złożoność czasowa O(n) O(log n) ✅
Wymaga sortowania ❌ NIE ✅ TAK
Prostota ✅ Bardzo proste Bardziej złożone
Małe dane (n < 20) ✅ Wystarczająco Overkill
Duże dane (n > 100) ❌ Wolne ✅ Bardzo szybkie

Przykład – różnica w wydajności:

13. Kiedy używać wyszukiwania liniowego?

✅ Używaj gdy:

  1. Lista nieposortowana (sortowanie kosztowne)
  2. Małe dane (n < 20) – różnica nieznaczna
  3. Jednorazowe wyszukiwanie (sortowanie + binarne > liniowe)
  4. Dane w strukturze nieliniowej (linked list)
  5. Szukasz wielu wystąpień

❌ Unikaj gdy:

  1. Duże dane (n > 100) + posortowane → użyj binarnego
  2. Wielokrotne wyszukiwania → posortuj raz, potem binarne

14. Benchmark

15. Zastosowania praktyczne

15.1. Filtrowanie listy

15.2. Sprawdzanie duplikatów

15.3. Wyszukiwanie w linked list

Uwaga: Linked list zawsze wymaga O(n) – nie ma szybszej metody!

16. Ćwiczenia

Zadanie 1: Znajdź minimum

Rozwiązanie

Zadanie 2: Sprawdź, czy posortowana

17. Podsumowanie

Wyszukiwanie liniowe:

  • Złożoność czasowa: O(n) – najgorszy i średni
  • Złożoność pamięciowa: O(1)
  • Wymaga sortowania: NIE ❌
  • Prostota: Bardzo prosty ✅

Zalety: - Najprostszy algorytm wyszukiwania - Nie wymaga sortowania - Działa dla dowolnej struktury (tablice, listy, linked lists) - O(1) pamięci - Można szukać wielu wystąpień

Wady: - Wolny dla dużych danych O(n) - Nie wykorzystuje uporządkowania (jeśli istnieje)

Kiedy używać: - ✅ Lista nieposortowana - ✅ Małe dane (n < 100) - ✅ Jednorazowe wyszukiwanie - ✅ Linked lists (nie ma lepszej metody) - ✅ Szukanie wszystkich wystąpień

Kiedy NIE używać: - ❌ Duże dane + posortowane → użyj binarnego O(log n) - ❌ Wielokrotne wyszukiwania → posortuj + binarne

Porównanie:

n = 1,000,000 elementów:
- Wyszukiwanie liniowe:  ~1,000,000 porównań
- Wyszukiwanie binarne:  ~20 porównań (50,000x szybsze!)

Co dalej warto poznać:

  • Wyszukiwanie binarne (O(log n) dla posortowanych)
  • Wyszukiwanie interpolacyjne
  • Jump search, exponential search
  • Hash tables (O(1) średnio!)
Wróć do spisu lekcji