Specjalny element w tablicy — największy, najmniejszy, lider

Po co się tego uczymy?

Znajdowanie największego, najmniejszego elementu czy "lidera" (wartości dominującej) w zbiorze danych to jedne z najczęściej sprawdzanych umiejętności algorytmicznych na maturze — a jednocześnie świetny wstęp do myślenia o złożoności obliczeniowej: to samo zadanie da się rozwiązać w O(n²) albo w O(n), jeśli wiesz, na co zwrócić uwagę.

Teoria

Największy element — myślenie "od środka": trzymaj NAJLEPSZY dotychczasowy wynik i porównuj go z kolejnymi elementami listy. Zaczynasz od pierwszego elementu jako "na razie największego", i za każdym razem, gdy trafisz na WIĘKSZY, podmieniasz. To działa w czasie O(n) — jedno pełne przejście listy (dokładnie tak samo działa wbudowana funkcja Pythona max()). Analogicznie działa szukanie najmniejszego elementu.

Indeks elementu — czasem potrzebujemy nie WARTOŚCI maksimum, tylko jej POZYCJI w liście (indeksu). Można znaleźć PIERWSZY indeks maksimum, albo WSZYSTKIE indeksy, pod którymi występuje wartość maksymalna (przydatne, gdy maksimum powtarza się kilka razy).

Lider to element, który występuje WIĘCEJ niż połowę długości listy. Np. w [2, 2, 1, 2, 3, 2, 2] liderem jest 2 (5 na 7 pozycji). Nie każda lista ma lidera!

Naiwne znalezienie lidera — sprawdzasz KAŻDEGO kandydata z listy i liczysz, ile razy występuje (L.count(kandydat)) — jeśli więcej niż n // 2, to lider. Czytelne, ale WOLNE: w najgorszym razie O(n²), bo count() też przechodzi całą listę, a robimy to dla KAŻDEGO elementu.

Szybsza wersja — algorytm Boyer-Moore — sprytny pomysł: parujemy RÓŻNE elementy i "kasujemy" je nawzajem, więc kandydatem zostaje to, czego zostaje NAJWIĘCEJ. Potem trzeba POTWIERDZIĆ kandydata osobnym liczeniem (bo sam algorytm może dać fałszywego kandydata, jeśli lidera w ogóle nie ma). Działa w O(n) — jedno przejście na znalezienie kandydata + jedno na potwierdzenie, czyli wciąż liniowo, a nie kwadratowo.

Przydatne przy testowaniu — przypadki brzegowe: pusta lista (zwracamy None / komunikat), wiele takich samych wartości (max/min działają normalnie, ale INDEKSÓW maksimum może być kilka), brak lidera to też POPRAWNY wynik (nie błąd).

Schemat

ZNAJDOWANIE MAX - "trzymaj najlepszy dotychczasowy wynik":
Lista: [5, 9, 2, 9, 3]
start: maks = 5
x=5: 5>5? nie      → maks=5
x=9: 9>5? tak      → maks=9
x=2: 2>9? nie      → maks=9
x=9: 9>9? nie      → maks=9
x=3: 3>9? nie      → maks=9        WYNIK: 9  (O(n) - jedno przejście)

BOYER-MOORE (lider) na [2,2,1,2,3,2,2]:
x=2: licznik=0→kandydat=2,licznik=1
x=2: ==kandydat→licznik=2
x=1: !=kandydat→licznik=1
x=2: ==kandydat→licznik=2
x=3: !=kandydat→licznik=1
x=2: ==kandydat→licznik=2
x=2: ==kandydat→licznik=3
Kandydat: 2 → potwierdzenie: count(2)=5 > 7//2=3 → LIDER = 2

Przykład z życia

System głosowania sprawdzający, czy jeden kandydat zdobył WIĘKSZOŚĆ (ponad połowę) głosów, to dokładnie problem "lidera" — a przy MILIONACH głosów różnica między algorytmem O(n²) a O(n) to różnica między liczeniem przez cały dzień a liczeniem w ułamku sekundy.

max_min_indeksy.py

# Największy i najmniejszy element - myślenie "od środka", O(n)
def znajdz_max(L):
    if not L:            # ochrona przed pustą listą
        return None
    maks = L[0]          # 1) start: pierwszy element
    for x in L:          # 2) idź po elementach
        if x > maks:     # 3) lepszy? podmień
            maks = x
    return maks          # 4) gotowe po jednym przejściu

def znajdz_min(L):
    if not L:
        return None
    mini = L[0]
    for x in L:
        if x < mini:
            mini = x
    return mini


# Indeks pierwszego maksimum
def indeks_max(L):
    if not L:
        return None
    m = L[0]
    idx = 0
    for i, x in enumerate(L):
        if x > m:
            m, idx = x, i
    return idx


# Wszystkie indeksy, pod którymi występuje maksimum
def indeksy_max(L):
    if not L:
        return []
    m = znajdz_max(L)
    return [i for i, x in enumerate(L) if x == m]

# Przykład: indeksy_max([3, 7, 7, 2, 7]) -> [1, 2, 4]

lider.py

# Lider - wersja naiwna, czytelna, ale O(n^2)
def znajdz_lidera_naiwny(L):
    n = len(L)
    for kandydat in L:                 # sprawdzamy kolejnych kandydatów
        if L.count(kandydat) > n // 2: # uwaga: // to dzielenie całkowite
            return kandydat
    return None


# Lider - algorytm Boyer-Moore, O(n) - szybszy dla dużych list
def znajdz_lidera_boyer_moore(L):
    # Faza 1: znajdź kandydata
    kandydat, licznik = None, 0
    for x in L:
        if licznik == 0:
            kandydat, licznik = x, 1
        elif x == kandydat:
            licznik += 1
        else:
            licznik -= 1

    # Faza 2: potwierdź kandydata (Faza 1 może dać "fałszywego" kandydata!)
    if kandydat is None:
        return None
    return kandydat if L.count(kandydat) > len(L)//2 else None


L1 = [2, 2, 1, 2, 3, 2, 2]
print(znajdz_lidera_naiwny(L1))       # 2
print(znajdz_lidera_boyer_moore(L1))  # 2

L2 = [1, 2, 3, 2, 1]
print(znajdz_lidera_naiwny(L2))       # None (brak lidera)

Komentarz i wyjaśnienie kodu

W znajdz_max() warunek if not L: return None to WAŻNE zabezpieczenie — pusta lista nie ma elementu maksymalnego, więc funkcja musi to jawnie obsłużyć, zamiast rzucić błąd przy próbie dostępu do L[0].

W algorytmie Boyer-Moore intuicja jest taka: jeśli JAKIŚ element występuje CZĘŚCIEJ niż połowa listy, to nawet gdy "kasujemy" go w parach z INNYMI, różnymi elementami, na końcu ZOSTANIE jako kandydat — bo par z innymi elementami po prostu nie starczy, żeby go całkowicie "wyzerować". Faza 2 (potwierdzenie przez count()) jest NIEZBĘDNA, bo dla list BEZ lidera (jak L2) faza 1 i tak zwróci JAKIEGOŚ kandydata — trzeba sprawdzić, czy naprawdę spełnia warunek "więcej niż połowa".

Ćwiczenie samodzielne

Uruchom obie wersje szukania lidera dla list L1 = [2, 2, 1, 2, 3, 2, 2] i L2 = [1, 2, 3, 2, 1] i sprawdź, że dają te same wyniki. Prześledź ręcznie na kartce, jak zmienia się kandydat i licznik w Boyer-Moore krok po kroku dla L1.

Zadania do pracy własnej

Wczytaj z klawiatury listę liczb (jedna linia, oddzielone spacjami) i wypisz największy i najmniejszy element BEZ używania wbudowanych funkcji max()/min() (napisz własną pętlę).
Napisz program, który podaje indeks PIERWSZEGO maksimum i indeks PIERWSZEGO minimum w liście — jeśli lista jest pusta, wypisz "brak danych". Następnie napisz funkcję wypisującą WSZYSTKIE indeksy, pod którymi występuje wartość maksymalna.
Zaimplementuj algorytm Boyer-Moore z fazą potwierdzenia i porównaj czas jego działania z wersją naiwną na DUŻEJ liście (np. 100 000 losowych liczb z domieszką wyraźnego lidera) — użyj modułu time i modułu random do wygenerowania danych testowych. O ile szybsza jest wersja Boyer-Moore?

Typowe błędy

Brak obsługi pustej listy — próba odczytania L[0] z pustej listy rzuci błąd IndexError; zawsze sprawdzaj if not L na początku.

Poleganie WYŁĄCZNIE na fazie 1 algorytmu Boyer-Moore, bez potwierdzenia — faza 1 zawsze zwróci JAKIEGOŚ kandydata, nawet jeśli lista NIE MA lidera; bez fazy 2 (potwierdzenia przez count()) wynik może być błędny.

Mylenie "brak lidera" z błędem programu — funkcja zwracająca None, gdy żaden element nie występuje więcej niż połowę długości listy, działa POPRAWNIE — to prawidłowy, oczekiwany wynik dla wielu list.

Nawiązanie do egzaminu zawodowego

Ten temat to praktyczne ćwiczenie ze złożoności obliczeniowej — to samo zadanie (znalezienie lidera) rozwiązane naiwnie (O(n²)) i sprytnie (Boyer-Moore, O(n)) pokazuje WYMIERNĄ różnicę wydajności, dokładnie tak jak w ostatniej lekcji tego działu o analizie algorytmów. W kolejnej lekcji poznasz algorytmy na grafach — strukturę danych, w której podobne pytania ("czy istnieje węzeł dominujący") pojawiają się w znacznie bardziej złożonym kontekście.