Linjär sökning

Linjär, sekventiell sökning är en algoritm för att hitta ett givet värde för en godtycklig funktion på ett visst intervall. Denna algoritm är den enklaste sökalgoritmen och lägger, till skillnad från till exempel binär sökning , inga begränsningar på funktionen och har den enklaste implementeringen. Sökningen efter ett funktionsvärde utförs genom att helt enkelt jämföra nästa värde som övervägs (som regel sker sökningen från vänster till höger, det vill säga från mindre värden av argumentet till större) och, om värdena matcha (med en eller annan noggrannhet), då anses sökningen vara avslutad.

Om segmentet har längden N är det möjligt att hitta lösningen upp till inom tiden . Den där. den asymptotiska komplexiteten hos algoritmen är . På grund av dess låga effektivitet jämfört med andra algoritmer används linjär sökning vanligtvis endast om söksegmentet innehåller mycket få element, dock kräver linjär sökning inte ytterligare minne eller funktionsbearbetning/analys, så det kan fungera i streaming-läge när man hämtar direkt data från vilken källa som helst. Linjär sökning används också ofta i form av linjära maximi/minimum sökalgoritmer. $\epsilon$ ${N \over \epsilon }$ $På)$

Som ett exempel kan vi betrakta sökningen efter värdet av en funktion på uppsättningen heltal som presenteras i en tabell.

Exempel

Variabler och innehåller, respektive, vänster och höger gränser för arraysegmentet, där elementet vi behöver finns. Forskning börjar med den första delen av segmentet. Om det sökta värdet inte är lika med värdet på funktionen vid den givna punkten, så utförs övergången till nästa punkt. Det vill säga, som ett resultat av varje kontroll reduceras sökområdet med ett element. $L$ $R$

int funktion LinearSearch(Array A, int L, int R, int Key); Börja för X = L till R gör om A[X] = tangent då returnera X returnera -1; // element hittades inte slutet;

Ett exempel i Swift 3, med "accelererad" sökning:

func linearSearch ( element : Int , i array : [ Int ]) -> Int ? { var array = array let realLastElement : Int ? om array . isEmpty { avkastning noll } annat { realLastElement = array [ array . räkna - 1 ] array [ array . räkna - 1 ] = element } var i = 0 ; while array [ i ] != element { i += 1 ; } let findedElement = array [ i ]; om i == array . count - 1 && foundedElement != realLastElement { avkastning noll } annat { returnera i } }

Analys

För en lista med n element är det bästa fallet ett där värdet du letar efter är lika med det första elementet i listan och endast en jämförelse krävs. Det värsta fallet är när det inte finns något värde i listan (eller det är i slutet av listan), i vilket fall n jämförelser behövs.

Om det önskade värdet finns i listan k gånger och alla förekomster är lika sannolika, då det förväntade antalet jämförelser

{\begin{cases}n&k=0\\[5pt]\displaystyle {\frac {n+1}{k+1}}&1\leq k\leq n.\end{cases}}

Till exempel, om det önskade värdet förekommer i listan en gång och alla förekomster är lika sannolika, då är det genomsnittliga antalet jämförelser . Men om det är känt att det inträffar en gång räcker det med n - 1 jämförelser, och det genomsnittliga antalet jämförelser kommer att vara lika med ${\frac {n+1}{2))$

\displaystyle {\frac {(n+2)(n-1)}{2n))

(för n = 2 är detta tal 1, vilket motsvarar en om-då-annan konstruktion).

I båda fallen är beräkningskomplexiteten för algoritmen O ( n ).

Applikationer

I allmänhet är en linjär sökning mycket enkel att implementera och är tillämpbar när listan innehåller få element, eller vid en enda sökning i en oordnad lista.

Om samma lista är tänkt att sökas igenom ett stort antal gånger, är det ofta meningsfullt att förbehandla listan, som att sortera och sedan använda en binär sökning , eller bygga en effektiv datastruktur för sökningen. Frekventa ändringar av listan kan också påverka valet av ytterligare åtgärder, eftersom det kräver en omstrukturering av strukturen.

Se även

Litteratur

Donald Knuth . The Art of Computer Programming, volym 3. Sortering och sökning = The Art of Computer Programming, vol.3. Sortering och sökning. - 2:a uppl. - M . : "Williams" , 2007. - S. 824. - ISBN 0-201-89685-0 .