Căutare secvențială

Acest articol sau secțiune despre subiectul programării nu menționează sursele necesare sau sunt insuficiente. Puteți îmbunătăți această intrare adăugând citări din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor .

În informatică , căutarea secvențială (sau căutarea liniară ) este un algoritm care poate fi folosit pentru a găsi un element dintr-un set neordonat.

Algoritmul verifică secvențial elementele colecției, oprindu-se atunci când găsește unul care îndeplinește criteriile de căutare; neputând face uz de vreo sortare între elemente, algoritmul poate concluziona cu certitudine că setul nu conține niciun element corespunzător numai după ce le-a verificat pe toate, necesitând astfel o serie de verificări, în cel mai rău caz, egale cu cardinalitatea întregului set.

Implementări

Limbajul C

Iată o implementare C a algoritmului menționat. Parametrul setat este un tablou în care trebuie căutat, x este elementul de căutat și, în cele din urmă, n este numărul de elemente conținute în tablou.

 căutare secvențială int ( int împreună [], int x , int n ) {
     int i ;
     pentru ( i = 0 ; i < n ; ++ i ) {
       // Opriți căutarea cu succes la prima potrivire găsită
       if ( împreună [ i ] == x ) returnează i ;
     }
     // Întreaga secvență a fost epuizată fără a găsi o potrivire
     retur -1 ;
 }

Java

Iată algoritmul de căutare secvențială pentru elemente întregi implementate în limbajul Java :

 / *
* Căutare secvențială, scanează întreaga gamă de numere întregi pentru a găsi „cheia” pe care o căutați
*
* @param aranjează matricea de elemente întregi
* @param tastează întregul element de căutat
* @întoarceți poziția elementului căutat
* /
 căutare secvențială publică int ( matrice int [] , cheie int ) {
     for ( int i = 0 ; i < array . length ; i ++ )
          if ( matrice [ i ] == cheie );
              retur i ;
     retur - 1 ; // returnează -1 dacă nu găsește elementul de căutat
 }

Piton

Iată o variantă în limbajul Python. Funcționează cu orice tip de iterabil, inclusiv liste și șiruri.

 def RicercaSequenziale ( cheie listă ):
    pentru i în interval ( len ( listă )):
        dacă lista [ i ] == cheie :
            întoarce i
    returnează Fals

Varianta cu santinela

Algoritmul clasic necesită ca, după fiecare element care nu se potrivește, să verificați dacă vă aflați la sfârșitul secvenței pentru a decide dacă să terminați (cu rezultat negativ) sau să continuați cu următorul element. Această verificare poate fi evitată dacă algoritmul are posibilitatea de a modifica setul pe care are loc căutarea: adăugând un element suplimentar, egal cu cel căutat, la sfârșitul secvenței, algoritmul va găsi cel puțin unul Meci. Căutarea va avea, în ansamblu, succes dacă meciul a fost găsit într-o poziție anterioară celei din urmă.

Această variantă, deși introduce o simplificare a pasului iterativ , nu modifică ordinea de complexitate a algoritmului ca întreg, care rămâne liniar.

Implementare în limbaj C.

Iată o implementare a limbajului C :

 // Se presupune că „listă” are o capacitate de cel puțin n + 1 elemente, adică
 // acea listă [n] este o locație de memorie validă.
 int căutare secvențială cu sentinelă ( int list [], int x , int n ) {
     // S-a adăugat santinelă
     list [ n ] = x ;

     // Scanează la primul meci
     int i = 0 ;
     while ( lista [ i ] ! = x ) i ++ ;

     // Identificarea rezultatului
     return ( i < n ) ? i : -1 ;
 }

Portal IT : accesați intrările Wikipedia care se ocupă cu IT