Sökalgoritmer – hitta rätt sak på rätt plats

Du har ett bibliotek med tusentals böcker. Hur hittar du rätt titel snabbast möjligt? Sökalgoritmer är vårt sätt att göra just det i koden – leta, verifiera och agera utan att slösa tid.

TL;DR

• Linjära sökningar går igenom varje post ett steg i taget – enkelt men långsamt.
• Binära sökningar halverar mängden kandidater vid varje steg – blixtsnabbt, men kräver sorterade listor.
• Välj sökstrategi utifrån hur data ser ut, hur ofta du söker och hur ofta du uppdaterar listan.

Efter det här avsnittet kan du

• Beskriva skillnaden mellan linjär och binär sökning i klartext.
• Implementera båda teknikerna i C# – med och utan generiska hjälpar-metoder.
• Veta när du ska satsa på standardbibliotek (t.ex. List<T>.BinarySearch) och när du ska rulla eget.
• Undvika klassiska fallgropar som 1-off fel (“off-by-one”) och binär sökning på osorterade listor.

Linjär sökning – allt på rad

Den mest “jordnära” algoritmen: gå från början till slut tills du hittar matchen. Perfekt när listan är kort eller nästan aldrig söks igenom.

public static int LinearSearch<T>(IEnumerable<T> source, T target)
    where T : IEquatable<T>
{
    int index = 0;
    foreach (var item in source)
    {
        if (item.Equals(target))
        {
            return index;
        }
        index++;
    }
    return -1; // hittade inget
}

Komplexitet: O(n) i värsta fall. Varje element besöks som mest en gång.

När den glänser:

• Korta listor eller engångssökningar.
• Strömmar av data där du inte kan hoppa (t.ex. någon läser från en fil rad för rad).
• När listan inte är sorterad och du inte vill sortera den (sortering kostar också tid).

Binär sökning – skär igenom listan

Binär sökning tänker mer som en detektiv: avfärda massor av kandidater i varje steg. Kräver att listan är sorterad, annars blir den lika förvirrad som en GPS utan satelliter.

public static int BinarySearch<T>(IList<T> source, T target)
    where T : IComparable<T>
{
    int left = 0;
    int right = source.Count - 1;

    while (left <= right)
    {
        int mid = left + ((right - left) / 2);
        int compare = source[mid].CompareTo(target);

        if (compare == 0)
        {
            return mid;
        }

        if (compare < 0)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    return -1; // hittade inget
}

Komplexitet: O(log n) – kraftigt mycket snabbare på stora, sorterade listor.

När den skiner:

• Stora mängder data som läses ofta men förändras sällan.
• Uppslag i försorterade kataloger, kundregister eller highscore-listor.
• När du behöver snabbt svar (typ “hitta användare” innan UI fryser).

Snabbguide: vilken ska jag välja?

Bonus: använd ramverket när du kan

Du behöver inte alltid rulla eget. C# har inbyggda metoder som gör grovjobbet:

var heroes = new List<string> { "Batman", "Flash", "Superman", "Wonder Woman" };
heroes.Sort(); // Sortera först!

int index = heroes.BinarySearch("Flash");
if (index >= 0)
{
    Console.WriteLine($"Flash hittades på index {index}");
}

Vill du bara veta om något finns? heroes.Contains("Flash") använder linjär sökning under huven. Byt listan mot HashSet<string> för O(1) i stället.

Vanliga misstag

• Glömmer att sortera innan binär sökning. Resultatet blir slump.
• Halverar fel: left + right / 2 kan overflowa vid extremt stora listor. Använd left + ((right - left) / 2).
• Överskattar linjär sökning – den kostar varje gång. Upprepar du sökningar: sortera, eller använd Dictionary.
• Jämför fel typ: Se till att din typ implementerar IComparable<T> eller att du skickar in en egen Comparer<T> när du använder ramverkets binärsök.

Vidareutveckling

• Kombinera sökningar med LINQ – FirstOrDefault, SingleOrDefault – men förstå att de fortfarande använder linjär logik.
• Använd Span<T>/ReadOnlySpan<T> för sökning i prestandakritiska loopar (mindre allocationer).
• Utforska mer avancerade strukturer (t.ex. B-träd, tries) när datastrukturen kan hjälpa dig ännu mer.

Övningar

1. Grön: Implementera linjär sökning som returnerar alla träffar (lista med index).
2. Gul: Skriv en binär sökning som tar en Comparison<T> så att du kan söka i både stigande och fallande listor.
3. Röd: Skapa en hjälparklass som automatiskt väljer sökstrategi baserat på listans storlek och om datat redan är sorterat.

Sammanfattning

• Linjär sökning är enkel men skalar dåligt.
• Binär sökning kräver sorterad data men är extremt snabb vid återkommande uppslag.
• C# erbjuder färdiga verktyg – använd dem, men förstå vad som händer under huven.
• Välj algoritm efter hur din data faktiskt används och uppdateras.

Dad joke (såklart)

Varför älskar binära sökningar logaritmer? För att de alltid hittar rätt gren i släktträdet.