INF.04 · C# · lekcja 27

Algorytmy wyszukiwania (liniowe i binarne)

Szukaj kolejno lub odrzucaj połowę

  • Zrozum
  • Sprawdź
  • Napisz sam

Po tej lekcji: szukaj kolejno lub odrzucaj połowę

Dzisiaj zrobisz konkretną rzecz

Wyszukiwanie elementu w zbiorze danych to jedna z najczęstszych operacji w programowaniu — szukanie użytkownika po ID, produktu po nazwie, słowa w słowniku. Podstawa programowa (INF.04.3.4) wymaga znajomości dwóch podejść o zupełnie różnej wydajności: wyszukiwania liniowego i binarnego — a wybór między nimi to praktyczne zastosowanie złożoności obliczeniowej z poprzedniej lekcji.

Szukanie słowa w papierowym słowniku — nikt nie sprawdza strony po stronie od początku (to byłoby wyszukiwanie liniowe). Zamiast tego otwieramy słownik mniej więcej w środku, sprawdzamy czy szukane słowo jest przed czy po tym miejscu, i powtarzamy w węższym zakresie — to dokładnie wyszukiwanie binarne wykonywane intuicyjnie przez człowieka od lat, zanim ktokolwiek nazwał to algorytmem.

Sprawdź w działaniu

Szukaj kolejno lub odrzucaj połowę

Najpierw przewidź wynik. Zmień dane w modelu i porównaj efekt. Spróbuj także przypadku granicznego, a nie tylko pierwszego poprawnego przykładu.

Ta interakcja wymaga włączonego JavaScriptu.

Model pokazuje wybraną zasadę. Nie uruchamia ani nie ocenia wklejonego kodu C#.

1. Przygotuj i uruchom własny projekt

2. Najpierw mały przykład

Wykonaj tę próbę przed dłuższym rozwiązaniem. Dane muszą być posortowane zgodnie z porównaniem. Po porównaniu usuwamy połowę przedziału. Wynik to indeks od0, a -1 oznacza brak. Nie myl indeksu z szukaną wartością.

Program.cscsharp
int[] liczby = { 2, 4, 6, 8, 10 };
int lewy = 0, prawy = liczby.Length - 1, indeks = -1;
while (lewy <= prawy)
{
    int srodek = lewy + (prawy - lewy) / 2;
    if (liczby[srodek] == 8) { indeks = srodek; break; }
    if (liczby[srodek] < 8) lewy = srodek + 1;
    else prawy = srodek - 1;
}
Console.WriteLine(indeks);
Wynik
3
  1. Co sprawdzić? Zmień jedną wartość i przed uruchomieniem zapisz przewidywany rezultat. Porównaj go z opisem wyniku; przy błędzie wróć do konkretnej instrukcji.

Jak to działa — 1

Wyszukiwanie liniowe — sprawdzamy po kolei każdy element zbioru, aż znajdziemy szukaną wartość albo dojdziemy do końca. Działa na DOWOLNYCH danych, posortowanych czy nie. Złożoność O(n) — w najgorszym przypadku (element na końcu albo nieobecny) trzeba sprawdzić wszystkie elementy.

Wyszukiwanie binarne — dużo szybsze (O(log n)), ale ma warunek: dane MUSZĄ być wcześniej posortowane. Algorytm sprawdza element w środku zakresu. Jeśli to szukana wartość — koniec. Jeśli szukana wartość jest mniejsza — cały zakres zawęża się do lewej połowy (bo w prawej połowie, jako że dane są posortowane, na pewno nie ma szukanej wartości). Jeśli większa — zawęża się do prawej połowy. Powtarzamy, aż znajdziemy wartość albo zakres się wyczerpie.

Każdy krok wyszukiwania binarnego odrzuca połowę pozostałych danych — dlatego dla miliona elementów potrzeba maksymalnie około 20 kroków (2²⁰ ≈ milion), podczas gdy wyszukiwanie liniowe w najgorszym przypadku potrzebowałoby miliona kroków. To ogromna różnica w praktyce.

Jak to działa — 2

Wybór metody to kompromis: jeśli dane zmieniają się rzadko, a wyszukujemy w nich często, warto je raz posortować i korzystać z szybszego wyszukiwania binarnego. Jeśli dane zmieniają się bardzo często (sortowanie za każdym razem miałoby swój koszt) albo zbiór jest mały, wyszukiwanie liniowe bywa prostszym i wystarczająco szybkim rozwiązaniem.

3. Pełny przykład — czytaj od Main

Teraz zastąp Program.cs tym programem. Zanim uruchomisz, znajdź dane wejściowe, operację i miejsce prezentacji wyniku. W tym wariancie zachowujemy jawny Main. Nie wklejaj kilku pełnych programów do jednego pliku.

Program.cs — osobne uruchomieniecsharp
using System;

class Program
{
    // Wyszukiwanie liniowe - O(n), działa na dowolnych (też nieposortowanych) danych
    static int WyszukiwanieLiniowe(int[] tab, int szukana)
    {
        for (int i = 0; i < tab.Length; i++)
        {
            if (tab[i] == szukana)
            {
                return i; // zwracamy indeks, w którym znaleziono
            }
        }
        return -1; // nie znaleziono
    }

    // Wyszukiwanie binarne - O(log n), WYMAGA posortowanej tablicy
    static int WyszukiwanieBinarne(int[] tab, int szukana)
    {
        int lewy = 0;
        int prawy = tab.Length - 1;

        while (lewy <= prawy)
        {
            int srodek = (lewy + prawy) / 2;

            if (tab[srodek] == szukana)
            {
                return srodek;
            }
            else if (tab[srodek] < szukana)
            {
                lewy = srodek + 1; // szukana jest w prawej połowie
            }
            else
            {
                prawy = srodek - 1; // szukana jest w lewej połowie
            }
        }

        return -1; // nie znaleziono
    }

    static void Main()
    {
        int[] posortowane = { 2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91 };

        Console.WriteLine("Liniowe, szukam 45: indeks " + WyszukiwanieLiniowe(posortowane, 45));
        Console.WriteLine("Binarne, szukam 45: indeks " + WyszukiwanieBinarne(posortowane, 45));
        Console.WriteLine("Binarne, szukam 99 (brak): indeks " + WyszukiwanieBinarne(posortowane, 99));
    }
}
  1. Prześledź kod WyszukiwanieLiniowe to prosta pętla — sprawdza każdy element po kolei, dopóki nie znajdzie szukanej wartości. WyszukiwanieBinarne utrzymuje dwie granice (lewy, prawy) wyznaczające aktualny zakres poszukiwań. W każdej iteracji liczy środek zakresu i porównuje wartość w środku z szukaną — jeśli szukana jest większa, cały zakres przesuwa się w prawo (lewy = srodek + 1), jeśli mniejsza — w lewo (prawy = srodek - 1). Pętla kończy się, gdy zakres "zniknie" (lewy > prawy), co oznacza, że elementu nie ma w tablicy.

Sprawdź, zanim przepiszesz cały program

Użycie wyszukiwania binarnego na nieposortowanych danych — algorytm zwróci błędny wynik (albo nie znajdzie istniejącego elementu), bo cała jego logika zakłada, że mniejsze wartości są po lewej, a większe po prawej stronie.

Nieskończona pętla przez błędną aktualizację granic — jeśli zapomni się +1 lub -1 przy aktualizacji lewy/prawy (czyli zostawi się lewy = srodek zamiast lewy = srodek + 1), pętla może nigdy się nie zakończyć.

Przepełnienie przy liczeniu środka dla bardzo dużych tablic — klasyczny wzorzec (lewy + prawy) / 2 teoretycznie może przepełnić zakres int dla ogromnych tablic; bezpieczniejszy zapis to lewy + (prawy - lewy) / 2. Dla typowych zadań szkolnych różnica jest czysto teoretyczna, ale warto wiedzieć, że taki problem istnieje.

Ćwiczenie z pomocą · samodzielna praca

4. Teraz Twoja zmiana

Dodaj licznik iteracji do obu funkcji wyszukiwania i porównaj, ile kroków potrzeba, żeby znaleźć ostatni element w tablicy 1000 elementów metodą liniową i binarną.

Oczekiwany rezultat
Spełnij warunki polecenia. Zapisz wejście, otrzymany wynik i wyjaśnij, która część kodu za niego odpowiada.
Potrzebujesz pomocy? Rozwiązuj krok po kroku.
Krok 1 — pokaż podpowiedź

Wróć do podstawowej formy oraz objaśnienia: Dane muszą być posortowane zgodnie z porównaniem. Po porównaniu usuwamy połowę przedziału. Wynik to indeks od0, a -1 oznacza brak. Nie myl indeksu z szukaną wartością.

Krok 2 — pokaż podpowiedź

Zmień tylko część potrzebną do polecenia. Zachowaj działającą wersję przed zmianą i uruchamiaj po każdym małym etapie.

Krok 3 — pokaż podpowiedź

Sprawdź przypadek zwykły i graniczny; porównaj z regułą: 3

Otwórz tylko tyle podpowiedzi, ile potrzebujesz. Po każdym kroku wróć do zadania i sprawdź wynik.

5. Sprawdź rozumienie, nie tylko uruchomienie

Dalej na swoim koncie

Rozgrzewki, quiz i zadania są w biurku ucznia.

Teoria jest otwarta dla wszystkich. Żeby rozwiązywać zadania, zapisywać szkice i widzieć swój postęp, zaloguj się.

Zaloguj się →
Źródła i dalsza nauka