Wyszukiwanie liniowe w C# – jak działa i kiedy go używać?

Wyszukiwanie liniowe w C# – jak działa i kiedy go używać?

Jeden z fundamentalnych algorytmów wyszukiwania. Prosty, intuicyjny i zaskakująco przydatny w codziennej pracy. Dowiedz się, jak go zaimplementować w C#, kiedy naprawdę warto po niego sięgnąć i dlaczego złożoność O(n) to nie zawsze wada.

Czym jest wyszukiwanie liniowe?

Wyobraź sobie, że szukasz konkretnej książki na nieuporządkowanej półce – zaczynasz od lewej i sprawdzasz każdą po kolei. Dokładnie tak działa wyszukiwanie liniowe (ang. linear search). To najprostszy możliwy algorytm wyszukiwania.

Algorytm przechodzi przez tablicę od indeksu 0 do n-1, porównując każdy element z szukaną wartością. Jak tylko znajdzie dopasowanie – zwraca jego indeks. Jeśli dotrze do końca bez powodzenia – zwraca -1.

💡 Dlaczego warto poznać ten algorytm?
Wyszukiwanie liniowe to punkt startowy do nauki złożoności obliczeniowej, analizy przypadków best/worst/average case i rozumienia, dlaczego struktura danych ma znaczenie. Każdy senior developer zna te podstawy na pamięć.

Jak działa? Wizualizacja krok po kroku

Weźmy tablicę z przykładu i poszukajmy elementu 50. Poniżej widać co algorytm robi na każdym kroku:

Tablica wejściowa – szukamy: 50 (oczekiwany indeks: 12)

Kluczowa obserwacja: algorytm natychmiast kończy pracę po znalezieniu elementu. Elementy pod indeksami 13 i 14 nie zostały w ogóle sprawdzone – to tak zwany early return.

Implementacja w C#

Podstawowa wersja

public static void Main()
{
    int[] array = { 30, 60, 80, 90, 130, 150, 210,
                     260, 400, 460, 20, 90, 50, 330, 220 };

    int searchValue = 50;
    int result = LinearSearch(array, searchValue);

    if (result == -1)
        Console.WriteLine($"Element {searchValue} nie występuje w tablicy.");
    else
        Console.WriteLine($"Element {searchValue} znaleziony na indeksie {result}.");
}

/// <summary>
/// Wyszukuje element w tablicy metodą liniową.
/// </summary>
/// <returns>Indeks elementu lub -1, jeśli nie znaleziono.</returns>
private static int LinearSearch(int[] array, int target)
{
    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] == target)
            return i; // early return – nie sprawdzamy reszty tablicy
    }

    return -1; // element nie istnieje w tablicy
}

Wyjście:

Element 50 występuje w tablicy pod indeksem 12
Element 100 nie występuje w tablicy

✅

Best practice – XML dokumentacja
W prawdziwych projektach zawsze dokumentuj metody przez /// <summary>. Dzięki temu IntelliSense pokaże opis w każdym miejscu użycia metody – oszczędza czas całego zespołu.

Analiza złożoności obliczeniowej

Złożoność obliczeniowa określa, jak rośnie czas wykonania algorytmu w zależności od rozmiaru danych wejściowych. Dla wyszukiwania liniowego:

Przypadek	Kiedy?	Złożoność	Przykład
Best Case	Element na pozycji 0	O(1)	Szukamy 30 → znalezione od razu
Average Case	Element gdzieś w środku	O(n/2)	Szukamy 50 → 13 porównań z 15
Worst Case	Element na końcu lub brak	O(n)	Szukamy 100 → 15 porównań, zwrot -1
Pamięć	Zawsze	O(1)	Tylko zmienna i w pętli

⚠️Ważna perspektywa
Złożoność O(n) dla małych zbiorów danych (do kilkuset elementów) jest w praktyce szybsza niż O(log n) – bo nie ma narzutu inicjalizacji i prosta pętla jest bardzo dobrze optymalizowana przez JIT. Mierz zanim oceniasz!

Edge case’y – co może pójść nie tak?

Przed wdrożeniem do prawdziwego projektu musisz obsłużyć przypadki brzegowe. Bazowa wersja nie broni się przed kilkoma scenariuszami:

// ❌ Tablice mogą być null – bazowa wersja rzuci NullReferenceException
int[] nullArray = null!;
LinearSearch(nullArray, 50); // 💥 crash

// ❌ Pusta tablica – pętla nie wykona się, ale czy kod to jasno komunikuje?
int[] emptyArray = [];
LinearSearch(emptyArray, 50); // Zwróci -1, ale czy tego oczekujesz?

// ❌ Duplikaty – bazowa wersja zwraca tylko PIERWSZY indeks
int[] dupeArray = { 90, 20, 90, 50 };
LinearSearch(dupeArray, 90); // Zwróci 0, nie 2

Defensywna wersja z guard clauses

private static int LinearSearch(int[] array, int target)
{
    // Guard clause: fail fast z czytelnym komunikatem
    ArgumentNullException.ThrowIfNull(array);

    if (array.Length == 0)
        return -1; // Pusta tablica – brak elementów do szukania

    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] == target)
            return i;
    }

    return -1;
}

💡 ArgumentNullException.ThrowIfNull() – nowość z .NET 6+
To statyczna metoda, która zastępuje klasyczny null-check w jednej linii.
Rzuca wyjątek z automatycznie uzupełnioną nazwą parametru – bez żadnego boilerplate’u.

Wersja generyczna – reużywalne rozwiązanie

Bazowa implementacja obsługuje tylko int[]. W realnym projekcie potrzebujesz algorytmu, który działa z dowolnym typem. Tu wchodzą typy generyczne:

/// <summary>
/// Generyczne wyszukiwanie liniowe. Działa z dowolnym typem implementującym IEquatable.
/// </summary>
public static int LinearSearch<T>(
    T[] array,
    T target,
    IEqualityComparer<T>? comparer = null)
{
    ArgumentNullException.ThrowIfNull(array);

    comparer ??= EqualityComparer<T>.Default;

    for (int i = 0; i < array.Length; i++)
    {
        if (comparer.Equals(array[i], target))
            return i;
    }

    return -1;
}

// Użycie z różnymi typami:
string[] names = { "Anna", "Bartek", "Celina" };
LinearSearch(names, "Bartek"); // → 1

// Case-insensitive – bez zmiany algorytmu!
LinearSearch(names, "bartek", StringComparer.OrdinalIgnoreCase); // → 1

double[] prices = { 9.99, 19.99, 4.49 };
LinearSearch(prices, 4.49); // → 2

✅ Dlaczego IEqualityComparer, a nie == ?
Operator == na typach generycznych nie działa bez constraintu. IEqualityComparer<T> daje elastyczność – możesz przekazać własną logikę porównania bez modyfikowania algorytmu. To wzorzec Strategy w miniaturze.

Alternatywy i kiedy je wybrać

Wyszukiwanie liniowe to nie jedyne narzędzie. Dobór algorytmu zależy od struktury i rozmiaru danych:

Linear SearchTwój wybór gdy

• Tablica nieposortowana
• Mały zbiór danych (<500)
• Wyszukiwanie jednorazowe
• Brak narzutu przygotowania
• Wolny dla dużych danych
• O(n) nawet przy duplikatach

Binary Search

• O(log n) – bardzo szybki
• Świetny dla dużych tablic
• Wymaga posortowanych danych
• Sortowanie kosztuje O(n log n)
• Bardziej złożona implementacja

Dictionary / HashSet

• O(1) lookup – najszybszy
• Idealne przy wielu wyszukiwaniach
• Zużywa więcej pamięci
• Wymaga wstępnego budowania struktury
• Nie zachowuje kolejności

⚠️ Praktyczna zasada w produkcji
Jeśli przeszukujesz tę samą kolekcję wielokrotnie w runtime – warto ją jednorazowo skonwertować do Dictionary<TKey, TValue>. Jednorazowa inwestycja O(n) na budowę słownika, a potem każde lookup kosztuje O(1). Klasyczny trade-off: pamięć vs czas.

Podsumowanie

⚡ Quick recap

• Wyszukiwanie liniowe iteruje tablicę od lewej do prawej, porównując każdy element z szukanym.
• Zwraca indeks pierwszego pasującego elementu lub-1gdy elementu nie ma.
• Złożoność czasowa: O(1) best case, O(n) worst case. Złożoność pamięciowa: O(1) zawsze.
• Używaj gdy tablica jest nieposortowana i mała – lub gdy szukasz jednorazowo.
• Do produkcji dodaj guard clauses (ArgumentNullException.ThrowIfNull) i obsługę pustej tablicy.
• Wersja generyczna zIEqualityComparer<T>działa z dowolnym typem i pozwala customizować logikę porównania.
• Dla dużych, często przeszukiwanych kolekcji – rozważDictionary(O(1)) lub posortowaną tablicę + Binary Search (O(log n)).

Wyszukiwanie liniowe to idealny punkt wejścia do świata algorytmów – prosty na tyle, żeby zrozumieć mechanizm, a jednocześnie na tyle realny, że pojawi się w każdym projekcie komercyjnym. Rozumiejąc jego ograniczenia, naturalne staje się sięganie po bardziej zaawansowane struktury danych we właściwym momencie.