Wyszukiwanie liniowe i binarne — porównanie algorytmów

Wyszukiwanie elementu na liście to klasyczny temat, na którym uczniowie po raz pierwszy zauważają, że dwa poprawne algorytmy mogą działać z bardzo różną szybkością. Zamiast mierzyć czas, w zadaniach liczymy porównania — wynik nie zależy od komputera i da się go sprawdzić na kartce.

Scenariusz jest przeznaczony na 45 minut dla klasy znającej pętle, listy i funkcje — na przykład po lekcji o sortowaniu bąbelkowym.

Przygotowanie stanowisk

Potrzebny jest Python 3 i edytor lub IDLE. Rozpakuj pakiet z sekcji materiałów do osobnego folderu. Program uruchomisz przez Run → Run Module albo poleceniem python start.py, python3 start.py lub py start.py.

Cele i plan lekcji

Po zajęciach uczeń potrafi:

• zapisać wyszukiwanie liniowe i zliczać jego porównania;
• wyjaśnić, dlaczego wyszukiwanie binarne wymaga listy posortowanej;
• zapisać wyszukiwanie binarne z granicami lewy i prawy;
• porównać liczby porównań w najgorszym przypadku dla obu metod.

Wyszukiwanie liniowe

Wyszukiwanie liniowe sprawdza elementy po kolei, od początku listy. Działa zawsze, także dla listy nieposortowanej, ale w najgorszym przypadku (szukany element na końcu albo brak elementu) wykonuje tyle porównań, ile jest elementów. W programie przerywamy pętlę, gdy znajdziemy szukaną wartość; jeśli pętla zakończy się bez przerwania, zwracamy −1.

Wyszukiwanie binarne

Wyszukiwanie binarne działa tylko na liście posortowanej. Porównujemy szukaną wartość ze środkiem przedziału: jeśli jest równa, koniec; jeśli szukana jest większa, odrzucamy lewą połowę (lewy = srodek + 1); jeśli mniejsza, odrzucamy prawą (prawy = srodek - 1). Każde porównanie zmniejsza przedział mniej więcej o połowę, więc dla 16 elementów wystarczy najwyżej 5 porównań, a dla 1000 elementów — około 10. Dla listy o n elementach to w przybliżeniu log₂(n) kroków.

Trzy zadania

Dane: dane = [3, 7, 9, 12, 15, 18, 21, 25, 30, 34, 41, 47, 52, 58, 63, 70] (16 posortowanych liczb).

Zadanie 1. Liniowe. Napisz liniowe(lista, szukana) zwracającą parę (indeks, liczba porównań) lub (−1, liczba porównań), gdy elementu brak. Sprawdź 15, 70 i 10.

Zadanie 2. Binarne. Napisz binarne(lista, szukana) zwracającą taką samą parę. Sprawdź te same wartości.

Zadanie 3. Najgorszy przypadek. Dla każdego elementu listy dane znajdź największą liczbę porównań obu metod. Następnie porównaj obie metody dla listy parzystych liczb range(0, 2000, 2) przy szukanej 1998.

Dla chętnych: sprawdź, że dane jest posortowana, a lista [9, 3, 7, 12] nie jest — i wyjaśnij, co poszłoby nie tak przy wyszukiwaniu binarnym w drugiej.

Rozwiązanie i wyniki

def liniowe(lista, szukana):
    porownania = 0
    for i in range(len(lista)):
        porownania = porownania + 1
        if lista[i] == szukana:
            return i, porownania
    return -1, porownania


def binarne(lista, szukana):
    lewy = 0
    prawy = len(lista) - 1
    porownania = 0
    while lewy <= prawy:
        srodek = (lewy + prawy) // 2
        porownania = porownania + 1
        if lista[srodek] == szukana:
            return srodek, porownania
        if lista[srodek] < szukana:
            lewy = srodek + 1
        else:
            prawy = srodek - 1
    return -1, porownania


dane = [3, 7, 9, 12, 15, 18, 21, 25, 30, 34, 41, 47, 52, 58, 63, 70]

# Zadanie 1
print(liniowe(dane, 15), liniowe(dane, 70), liniowe(dane, 10))

# Zadanie 2
print(binarne(dane, 15), binarne(dane, 70), binarne(dane, 10))

# Zadanie 3
najgorzej_l = max(liniowe(dane, x)[1] for x in dane)
najgorzej_b = max(binarne(dane, x)[1] for x in dane)
print("Najgorszy przypadek:", najgorzej_l, najgorzej_b)
duze = list(range(0, 2000, 2))
print(len(duze), liniowe(duze, 1998)[1], binarne(duze, 1998)[1])

Program wypisze:

(4, 5) (15, 16) (-1, 16)
(4, 4) (15, 5) (-1, 4)
Najgorszy przypadek: 16 5
1000 1000 10

Dla szukanej 15 wyszukiwanie liniowe potrzebuje 5 porównań, a binarne 4; dla 70 (ostatni element) liniowe aż 16, a binarne 5. W zadaniu 3 różnica rośnie: na liście 1000 elementów liniowe wykonuje 1000 porównań, a binarne zaledwie 10 (wartości zweryfikowano uruchomieniem). Zadanie dla chętnych wypisuje:

True False

Typowe błędy

Pytania kontrolne i punktacja

1. Dlaczego wyszukiwanie binarne wymaga listy posortowanej?
2. Ile porównań w najgorszym przypadku potrzeba dla listy 16 elementów w wyszukiwaniu binarnym?
3. Kiedy wyszukiwanie liniowe jest lepszym wyborem?

Odpowiedzi: Odrzucenie połowy opiera się na założeniu, że po jednej stronie środka są mniejsze, a po drugiej większe wartości. Pięć. Gdy lista jest nieposortowana, krótka lub szukamy tylko raz — sortowanie kosztowałoby więcej niż samo przeszukanie.

Proponowana punktacja (razem 10 punktów): zadanie 1 — pętla i zwrot indeksu 1 pkt, licznik i brak elementu 1 pkt; zadanie 2 — granice 2 pkt, środek i porównania 2 pkt; zadanie 3 — najgorszy przypadek obu metod 2 pkt, porównanie dla dużej listy 1 pkt, poprawne wyniki zadań 1–2 1 pkt. Zadanie dla chętnych nie jest wymagane do pełnej oceny.

Materiały do pobrania

• Pakiet Python: plik startowy, rozwiązanie, rozszerzenie i karta pracy
• Karta pracy ucznia — otwórz i wydrukuj

Rozpakuj ZIP przed otwarciem skryptów. Materiały są dostępne bez logowania; publiczne rozwiązanie służy nauce i samodzielnemu sprawdzeniu, a nie poufnemu sprawdzianowi.

Co dalej po wyszukiwaniu?

Kolejne tematy to złożoność obliczeniowa, sortowanie szybkie i wyszukiwanie w słownikach. Ten materiał rozwija dział o algorytmach w kursie Informatyka w TablicaPro, gdzie znajdziesz prezentacje, ćwiczenia i testy do prowadzenia lekcji.

Źródła techniczne: wyszukiwanie binarne w Wikipedii oraz moduł bisect w dokumentacji Pythona. Zobacz też lekcję o listach w Pythonie.