Algorytmy wyszukiwania (liniowe i binarne)

Po co się tego uczymy?

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.

Teoria

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.

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.

Schemat

Wyszukiwanie binarne szukanej wartości 23 w POSORTOWANEJ tablicy:

[2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91]
 0  1  2  3   4   5   6   7   8   9   10

Krok 1: środek = indeks 5, wartość 23 -> ZNALEZIONO od razu!

A gdybyśmy szukali 45:
Krok 1: środek (indeks 5) = 23, szukane 45 > 23 -> odrzuć LEWĄ połowę
        [38, 45, 56, 72, 91]   (indeksy 6-10)
Krok 2: środek (indeks 8) = 56, szukane 45 < 56 -> odrzuć PRAWĄ połowę
        [38, 45]               (indeksy 6-7)
Krok 3: środek (indeks 6) = 38, szukane 45 > 38 -> odrzuć lewą
        [45]                   ZNALEZIONO

Każdy krok odrzuca połowę pozostałych danych -> O(log n)

Przykład z życia

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.

Kod (C#)

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 = ; 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 = ;
        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));
    }
}

Komentarz i wyjaśnienie kodu

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.

Ćwiczenie samodzielne

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ą.

Plac zabaw — wypróbuj online

Poniższy kod wykonuje się od razu w Twojej przeglądarce — nic nie trzeba instalować. Zmień kod i kliknij „Uruchom”.

CSHARP

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));
    }
}

Zadania do pracy własnej

Napisz funkcję WyszukiwanieLiniowe dla tablicy tekstów (string[]) zamiast liczb — powinna zwracać indeks pierwszego dopasowania.
Napisz funkcję WyszukiwanieBinarneRekurencyjne — tę samą logikę wyszukiwania binarnego, ale zapisaną rekurencyjnie (nawiązanie do lekcji 20) zamiast pętlą while.
Zaimplementuj wyszukiwanie binarne "najbliższej wartości" — jeśli dokładnej wartości nie ma w tablicy, funkcja powinna zwrócić indeks elementu najbliższego szukanej wartości (a nie -1).

Typowe błędy

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.

Nawiązanie do egzaminu zawodowego

To druga część efektu INF.04.3.4 — "stosuje algorytmy sortowania i wyszukiwania". Wyszukiwanie binarne jest też konkretnym przykładem złożoności O(log n) z lekcji 24 i naturalnie łączy się z sortowaniem z lekcji 26 — bo bez wcześniejszego posortowania danych wyszukiwanie binarne w ogóle nie zadziała poprawnie.