Linjär sökning

Linjärsökning kontrollerar värden ett i taget tills målet hittas eller samlingen tar slut. Den fungerar på osorterad indata och kan användas för arrayer, länkade listor och strömmar. Till skillnad från binärsökning krävs varken sortering eller direkt indexering.

Exempel steg för steg

För [7, 4, 9, 2] och målet 9 jämförs först 7, sedan 4 och till sist 9. Första träffen ligger på index 2, eftersom index börjar på noll. Om du söker efter 5 kontrolleras alla fyra värden och funktionen returnerar -1 när värdet saknas.

C# och C++

C#

C# | LinearSearch.cs

public static int FindIndex(int[] values, int target)
{
    ArgumentNullException.ThrowIfNull(values);
    for (int i = 0; i < values.Length; i++)
    {
        if (values[i] == target) return i;
    }
    return -1;
}

C++

C++ | LinearSearch.cpp

#include <vector>
#include <cstddef>

int findIndex(const std::vector<int>& values, int target) {
    for (std::size_t i = 0; i < values.size(); ++i) {
        if (values[i] == target) return static_cast<int>(i);
    }
    return -1;
}
// For collections larger than INT_MAX, use an optional<size_t> result.

Båda funktionerna går från vänster till höger och returnerar index för första träffen. C# kontrollerar null-indata. C++ använder en referens till en vector som antas finnas. Returtypen int är enkel för små listor, men riskerar overflow för enorma samlingar. Ett större produktions-API kan använda std::optional<std::size_t> i stället för -1.

Tid och minne

Fall	Jämförelser	Komplexitet
Första värdet matchar	1	O(1) tid i bästa fall
Sista värdet matchar	n	O(n) tid i värsta fall
Målet saknas	n	O(n) tid i värsta fall

Om målet är jämnt fördelat bland n positioner och alltid finns blir det förväntade antalet jämförelser ungefär (n + 1) / 2, fortfarande O(n). Det genomsnittsantagandet gäller inte alla dataset. Båda implementationerna använder O(1) extraminne. Om alla matchande index lagras behövs extra minne proportionellt mot resultatet.

Korrekthet och gränsfall

För en tom samling returneras -1 utan indexering. Om värdet finns flera gånger returneras första positionen. För redan sorterad data med effektiv indexering kan binärsökning ge O(log n) jämförelser, förutsatt att sorteringskravet är uppfyllt.

Övning: Använd [4, 4, 8, 11, 4]. Förutsäg index när du söker efter 4, 8 och 7, och räkna jämförelser. Jämför sedan i Big O-utforskaren.