Introducere în algoritmul de căutare liniară: introducere și caracteristici[cu exemple]

Ce este căutarea?

Căutarea este procesul de găsire a unui element dat într-o listă de elemente. Ajută la căutarea unei anumite înregistrări. Prin urmare, este o tehnică de identificare a locului unui articol dat. Succesul unui proces de căutare depinde dacă elementul care trebuie căutat a fost identificat sau nu.

Structura de date permite căutarea datelor prin două metode.

1. Căutare liniară sau căutare secvențială
2. Căutare binară

Căutare liniară

Algoritmii de căutare liniară sunt un tip de algoritm pentru căutarea secvenţială a datelor. Acest algoritm găsește un element dat cu complexitate O(n). Se aplică unei colecții de articole. Fiecare element al datelor este căutat secvenţial şi returnat dacă se potriveşte cu elementul căutat. Dacă nu se găsesc potriviri, atunci căutarea continuă până la sfârșitul datelor colectate. Practic, este o tehnică de explorare a fiecărui element în timp ce parcurgeți lista. Algoritmul de căutare poate fi aplicat atât datelor sortate, cât și celor nesortate. Căutarea practic liniară este rar utilizată din cauza opțiunilor de căutare mai rapide oferite de alți algoritmi de căutare, cum ar fi algoritmii de căutare binari și hashtables.

Pași în algoritmul de căutare liniară

• Citirea elementului de căutare de către utilizator.
• Elementul de căutat este comprimat cu primul element al listei.
• Dacă elementele se potrivesc, atunci se generează un randament.
• Dacă elementele nu se potrivesc, atunci elementul de căutat este comparat cu al doilea element al listei.
• Procesul se repetă până când elementul este potrivit.

Caracteristicile algoritmilor de căutare liniară

1. Se aplică de obicei unei liste mici de date nesortate sau neordonate.
2. Timpul este dependent liniar de numărul de elemente, deci având o complexitate temporală dacă O(n).
3. Implementarea este foarte simplă.

Algoritmi de căutare liniară

O metodă de buclă continuă continuă dacă și până când elementul este găsit

• algoritmul Seqnl_Search(listă, articol)
• Pre: lista != ;
• Postare: returnați indexul articolului dacă este găsit, în caz contrar: 1
• indice <- fi
• while index < list.Cnt și list[index] != item //cnt: variabilă contor
• indice <- indice + 1
• sfârşitul în timp ce
• dacă index < list.Cnt și list[index] = item
• indice de returnare
• sfârşitul dacă
• întoarcere: 1
• terminați Seqnl_Search

Exemplu de căutare liniară

Problemă: Având în vedere o matrice arr[] de n elemente, scrieți o funcție pentru a căuta un element dat x în arr[].

Figura 1: Un exemplu de cod care arată implementarea algoritmului de căutare liniară

Sursă

Algoritmii de căutare liniară pot fi utilizați în mai multe limbaje de programare.

1. Căutare liniară în Python

Figura 2: Un exemplu de cod care arată un algoritm de căutare liniară în limbajul Python

Sursă

Ieșire: elementul este prezent la indicele 3

2. Căutare liniară în C

Figura 3: Un exemplu de cod care arată un algoritm de căutare liniară în limbajul C

Sursă

Ieșire : elementul este prezent la indicele 3

3. Căutare liniară în structura datelor

Pseudocod pentru o problemă de căutare liniară în structura datelor este

Figura 4: Pseudocodul pentru algoritmul de căutare liniară

Sursă

Căutare binară

Căutarea binară este un algoritm de căutare a elementelor dintr-o serie de elemente. În comparație cu algoritmul de căutare liniară, algoritmul de căutare binar este aplicat unei liste sortate de date.

Algoritmul de căutare binar include următorii pași

• Comparația elementului de căutat cu elementul din mijlocul listei sau al tabloului.
• Dacă elementul se potrivește cu elementul din listă, returnează indexul elementului din mijloc.
• Dacă nu se returnează nicio potrivire, se verifică dacă elementul este mai mare sau mai mic decât elementul din mijloc.
• Pentru un element de valoare mai mare decât elementul din mijloc, căutarea este efectuată în partea dreaptă a matricei.
• În mod similar, dacă elementul are o valoare mai mică decât elementul din mijloc, atunci căutarea este efectuată în partea stângă a listei.

Prin urmare, căutarea binară se aplică cel mai bine atunci când datele conțin un număr mare de elemente tijă într-o manieră sortată. Acest lucru face o cerință pentru algoritmul de căutare ca lista/matricea să fie sortată.

Caracteristicile Căutării binare

• Algoritmul de căutare binar este util pentru căutarea unui număr mare de elemente dintr-o matrice.
• Algoritmul de căutare binar are o complexitate de timp de O(logn).
• Implementarea unui algoritm de căutare binar este simplă.

Algoritmul de căutare binar

• Algoritmul Binary_Search(listă, articol)
• Setați L la 0 și R la n: 1
• dacă L > R, atunci Binary_Search se încheie ca nereușit
• altfel
• Setați m (poziția din elementul central) la podeaua (L + R) / 2
• dacă Am < T, setați L la m + 1 și treceți la pasul 3
• dacă Am > T, setați R la m: 1 și treceți la pasul 3
• Acum, Am = T,
• căutarea este făcută; întoarcere (m)

Concluzie

În acest articol, am analizat ce este un algoritm de căutare liniară și, de asemenea, am studiat în detaliu cum să căutăm un anumit element dintr-o listă folosind algoritmul de căutare liniară. În cele din urmă, am văzut și cum am putea implementa practic algoritmul de căutare liniară folosind Python 3 ca limbaj și să obținem rezultatul dorit.

Dacă sunteți interesat de Data Science, trebuie să consultați Programul Executive PG în Data Science al IIIT-B și upGrad, care a fost creat cu atenție pentru profesioniștii care lucrează și oferă numeroase studii de caz, ateliere practice, mentorat individual și mult mai mult.