Căutare liniară

Căutarea liniară, secvenţială este un algoritm pentru găsirea unei valori date a unei funcţii arbitrare pe un anumit interval. Acest algoritm este cel mai simplu algoritm de căutare și, spre deosebire de, de exemplu, căutarea binară , nu impune nicio restricție asupra funcției și are cea mai simplă implementare. Căutarea unei valori a funcției se realizează prin simpla comparare a următoarei valori luate în considerare (de regulă, căutarea are loc de la stânga la dreapta, adică de la valori mai mici ale argumentului la cele mai mari) și, dacă valorile potrivire (cu una sau alta precizie), atunci căutarea este considerată finalizată.

Dacă segmentul are lungimea N, atunci este posibil să găsiți soluția până în intervalul de timp . Acea. complexitatea asimptotică a algoritmului este . Datorită eficienței sale scăzute în comparație cu alți algoritmi, căutarea liniară este utilizată de obicei doar dacă segmentul de căutare conține foarte puține elemente, totuși, căutarea liniară nu necesită memorie suplimentară sau procesare/analizare a funcției, astfel încât poate funcționa în modul streaming atunci când obțineți direct date din orice sursă. De asemenea, căutarea liniară este adesea folosită sub formă de algoritmi liniari de căutare maxim/minim. $\epsilon$ ${N \over \epsilon }$ $Pe)$

Ca exemplu, putem considera căutarea valorii unei funcții pe mulțimea de numere întregi prezentate într-un tabel.

Exemplu

Variabile și conțin, respectiv, limitele din stânga și din dreapta ale segmentului de matrice, unde se află elementul de care avem nevoie. Cercetarea începe cu primul element al segmentului. Dacă valoarea căutată nu este egală cu valoarea funcției la punctul dat, atunci se efectuează tranziția la următorul punct. Adică, în urma fiecărei verificări, zona de căutare este redusă cu un element. $L$ $R$

funcția int LinearSearch(Matrice A, int L, int R, int Key); ÎNCEPE pentru X = L la R do dacă A[X] = cheie atunci întoarce X întoarcere -1; // elementul nu a fost găsit Sfârşit;

Un exemplu în Swift 3, cu căutare „accelerată”:

func linearSearch ( element : Int , în matrice : [ Int ]) -> Int ? { var array = matrice lasă realLastElement : Int ? if array . este gol { returnează zero } altfel { realLastElement = matrice [ matrice . numără - 1 ] matrice [ matrice . count - 1 ] = element } var i = 0 ; while array [ i ] != element { i += 1 ; } fie findedElement = matrice [ i ]; dacă i == matrice . count - 1 && foundedElement != realLastElement { returnează zero } altfel { intoarce i } }

Analiză

Pentru o listă de n elemente, cel mai bun caz este acela în care valoarea pe care o căutați este egală cu primul element al listei și este necesară o singură comparație. Cel mai rău caz este atunci când nu există nicio valoare în listă (sau este la sfârșitul listei), caz în care sunt necesare n comparații.

Dacă valoarea dorită este în lista de k ori și toate aparițiile sunt la fel de probabile, atunci numărul așteptat de comparații

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

De exemplu, dacă valoarea dorită apare în listă o dată și toate aparițiile sunt la fel de probabile, atunci numărul mediu de comparații este . Cu toate acestea, dacă se știe că apare o dată, atunci n - 1 comparații sunt suficiente, iar numărul mediu de comparații va fi egal cu ${\frac {n+1}{2))$

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

(pentru n = 2, acest număr este 1, care corespunde unui construct dacă-atunci-altfel).

În ambele cazuri, complexitatea de calcul a algoritmului este O ( n ).

Aplicații

În general, o căutare liniară este foarte simplu de implementat și este aplicabilă atunci când lista conține puține elemente, sau în cazul unei singure căutări într-o listă neordonată.

Dacă aceeași listă ar trebui căutată de un număr mare de ori, atunci este adesea logic să preprocesați lista, cum ar fi sortarea și apoi utilizarea unei căutări binare sau construirea unei structuri de date eficiente pentru căutare. Modificarea frecventă a listei poate influența și alegerea acțiunilor ulterioare, deoarece necesită procesul de restructurare a structurii.

Vezi și

Literatură

Donald Knuth . The Art of Computer Programming, Volumul 3. Sorting and Searching = The Art of Computer Programming, vol.3. Sortare și căutare. - Ed. a II-a. - M . : „Williams” , 2007. - S. 824. - ISBN 0-201-89685-0 .