Wyszukiwanie liniowe

🎯 Po co Ci to?

Szukasz biletu w stercie papierów na biurku. Nie ma sprytnego sposobu — bierzesz kartkę po kartce, aż trafisz. To jest wyszukiwanie liniowe: najprostszy algorytm świata, którego… wciąż używa się miliardy razy dziennie, bo na danych nieuporządkowanych nic lepszego nie istnieje. Dziś doszlifujesz je do perfekcji — a w rozszerzeniu poznasz wartownika: mikrosprytną sztuczkę, która pokazuje, że nawet w najprostszym algorytmie jest miejsce na elegancję.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • napisać wyszukiwanie liniowe zwracające pozycję elementu (lub sygnał braku);
  • policzyć koszt: najlepszy, najgorszy i typowy przypadek;
  • (w rozszerzeniu) zastosować technikę wartownika i wyjaśnić, co oszczędza.

🔁 Przypomnij sobie

Z 3.4: lista, indeksy, pętla po indeksach; z 5.2: $-1$ jako umowny sygnał „nie znaleziono" i ewakuacja return w środku pętli.

📘 Wyjaśnienie

Specyfikacja: dane — lista $L$ ($n$ elementów) i wartość $x$; wynik — indeks pierwszego wystąpienia $x$ w $L$ albo $-1$.

def szukaj(L, x):
    for i in range(len(L)):
        if L[i] == x:
            return i          # trafiony — natychmiast wychodzimy
    return -1                 # przeżyliśmy całą pętlę — nie ma

Sześć linijek bez tajemnic — ale koszt ma trzy twarze. Najlepszy przypadek: $x$ na początku — jedno porównanie. Najgorszy: $x$ na końcu albo go nie ma — $n$ porównań. Typowy (element jest, pozycja losowa): średnio $n/2$. Od tej jednostki nawyk zawodowca brzmi: o koszcie algorytmu mów trzema liczbami, nie jedną — a przynajmniej wiedz, którą z trzech podajesz.

Czy da się szybciej? Na liście nieuporządkowanej — nie, i to z twardym argumentem (znasz go z zadania w 1.5): każdy nieobejrzany element może być tym szukanym, więc algorytm, który czegoś nie obejrzał, można oszukać. Dolna granica: $n$ porównań w najgorszym przypadku. Kropka. Całe przyspieszanie wyszukiwania — binarne (6.2), haszowanie (5.6), indeksy baz danych (dział 12) — polega na przygotowaniu danych zawczasu, nie na sprytniejszym oglądaniu.

💭 Pomyśl: Lista ocen całej szkoły ma 50 000 wpisów. Sekretariat szuka po numerze PESEL ucznia — kilkaset razy dziennie. Czy wyszukiwanie liniowe to dobry wybór? Od czego zależy odpowiedź?

Sprawdź odpowiedź

Pojedyncze szukanie: 50 000 porównań — dla komputera ułamek milisekundy, żaden problem. Kilkaset dziennie — wciąż nic. Ale zmień skalę (ZUS: miliony rekordów, miliony zapytań dziennie) i liniowe umiera. Odpowiedź zależy od iloczynu (rozmiar × częstość szukań): mały iloczyn → liniowe i nie kombinuj; duży → zainwestuj w porządek (6.2) albo strukturę (dział 12). Dobry inżynier nie zna „najlepszego algorytmu" — zna próg, przy którym zmienia algorytm.

[R] Wartownik. Spójrz jeszcze raz na pętlę: w każdym obrocie wykonują się dwa porównania — jawne L[i] == x i ukryte sprawdzenie i < len(L), którym pętla pilnuje końca listy. Połowa pracy idzie na pilnowanie granicy! Sztuczka wartownika: dostaw $x$ na koniec listy — teraz pętla na pewno kiedyś trafi $x$, więc granicy nie trzeba pilnować wcale:

def szukaj_wartownik(L, x):
    L.append(x)                   # wartownik: gwarantowane trafienie
    i = 0
    while L[i] != x:              # JEDNO porównanie na obrót — bez pilnowania końca
        i = i + 1
    L.pop()                       # sprzątamy wartownika (pop zdejmuje ostatni)
    if i < len(L):
        return i                  # trafienie przed wartownikiem — prawdziwe
    return -1                     # trafiliśmy dopiero wartownika — x nie było

Wynik identyczny, porównań o połowę mniej. Wartownik nie zmienia klasy kosztu (wciąż liniowo), ale ścina stałą — a przy pętli wykonywanej miliardy razy stała to realne watogodziny. Ważniejsza jednak jest idea: zamiast sprawdzać warunek brzegowy w każdym obrocie, przygotuj dane tak, by brzeg obsłużył się sam. Ten manewr spotkasz w scalaniu (6.6), w listach z głowicą (dział 9) i w niejednym zadaniu maturalnym.

🐞 Znajdź błąd

Funkcja ma zwracać indeks ostatniego wystąpienia $x$:

def szukaj_ostatni(L, x):
    for i in range(len(L)):
        if L[i] == x:
            wynik = i
    return wynik

Dla ([3, 7, 3], 3) zwraca 2 — działa! Znajdź dane, na których program padnie (nie: skłamie — padnie), i podaj poprawkę.

Sprawdź odpowiedź

Gdy $x$ nie występuje wcale (np. ([1, 2], 9)), przypisanie wynik = i nigdy się nie wykona — a return wynik sięga po zmienną, która nie istnieje: NameError. Poprawka: wynik = -1 przed pętlą (wzorzec „wyzeruj przed, aktualizuj w środku" z 3.3 — tu „zerem" jest sygnał braku). Błąd należy do ulubionej rodziny „ścieżka, o której nikt nie pomyślał" — i wykrywa go koszyk testów „elementu nie ma", który od 3.6 masz w standardzie.

🛠️ Teraz Ty

Napisz szukaj_wszystkie(L, x) zwracające listę wszystkich indeksów wystąpień oraz ile_wystapien(L, x) — i zdecyduj, która z nich powinna wywoływać którą (a może żadna żadnej?). Przetestuj na liście z powtórzeniami i bez wystąpień. [R] Dopisz wersję z wartownikiem i porównaj liczbę porównań na liście 10⁶ elementów bez szukanego elementu.

📐 Definicje tej lekcji

  • Wyszukiwanie liniowe — przegląd elementów po kolei z ewakuacją przy trafieniu; koszt: 1 / $n/2$ / $n$ (najlepszy/typowy/najgorszy).
  • [R] Wartownik — element-strażnik dostawiony na koniec, gwarantujący trafienie; zdejmuje sprawdzanie granicy z każdego obrotu.

📌 Najważniejsze w pigułce

  • Na danych bez porządku nic nie pobije liniowego — dolna granica to obejrzenie wszystkiego.
  • Koszt podawaj w trzech przypadkach; „średnio $n/2$" i „najgorzej $n$" to różne zdania.
  • Przyspieszenie wyszukiwania zawsze kupuje się wcześniejszym przygotowaniem danych.

🎒 Zadania

  1. Lista ma 1000 elementów. Ile porównań L[i] == x wykona szukaj, gdy: (a) $x$ jest na pozycji 0, (b) na pozycji 999, (c) nie ma go, (d) występuje na pozycjach 4 i 500?
Wskazówka i odpowiedź

(a) 1; (b) 1000; (c) 1000; (d) 5 — funkcja zwraca pierwsze wystąpienie i ewakuuje się natychmiast; drugie wystąpienie jest niewidzialne. Przypadki (b) i (c) kosztują tyle samo, choć wyniki są skrajnie różne — koszt i wynik to osobne kategorie.

  1. Kolega twierdzi: „posortuję listę raz, a potem będę szukał liniowo — będzie szybciej, bo posortowana!". Oceń rozumowanie.
Wskazówka i odpowiedź

Samo posortowanie nie przyspiesza liniowego ani o jotę — ono i tak ogląda po kolei (no, może przerwie wcześniej, gdy minie miejsce, gdzie $x$ powinien być: to daje średnio $n/2$ zamiast $n$ przy braku elementu — coś tam jest). Prawdziwy zysk z porządku bierze dopiero algorytm, który umie go wykorzystać: binarne z 6.2 zejdzie do $\log n$. Porządek to paliwo; trzeba jeszcze silnika.

  1. [R] W wersji z wartownikiem ktoś „posprzątał" kod i usunął linijkę L.pop(). Testy przechodzą. Jaki paskudny błąd właśnie powstał i czemu testy milczą?
Wskazówka i odpowiedź

Każde wywołanie doleja jeden element do listy wywołującego (pamiętasz z 3.4: lista to wspólny obiekt, nie kopia!). Po tysiącu szukań lista ma tysiąc śmieciowych ogonów — rosnąca pamięć, fałszywe wystąpienia, chaos. Testy milczą, bo sprawdzają wynik funkcji, nie stan danych po niej. Morał podwójny: funkcja nie powinna zostawiać śladów w cudzych danych (a jeśli musi — sprzątać po sobie), a testy powinny zaglądać także do danych po wywołaniu.

🔍 Sprawdź, czy umiesz

  • Napisać wyszukiwanie liniowe z pamięci — z sygnałem braku i ewakuacją.
  • Podać koszt w trzech przypadkach i uzasadnić dolną granicę $n$.
  • [R] Wyjaśnić wartownika: co dokłada, co zdejmuje, dlaczego musi posprzątać.

Ucz się tej jednostki z asystentem