Căutarea în structura datelor: diferite metode de căutare explicate
Publicat: 2021-05-03Rețeaua de comunicații se extinde, așa că oamenii folosesc internetul! Afacerile se digitalizează pentru un management eficient. Datele generate pe internet sunt în creștere și, astfel, seturile de date devin complexe. Este esențial să organizați, să gestionați, să accesați și să analizați datele cu atenție și eficiență, o structură de date este cea mai utilă tehnică, iar articolul se concentrează pe aceeași!
Cuprins
Structură de date
În informatică, structurile de date sunt baza pentru tipurile de date abstracte (ADT), unde ADT sunt forma logică a tipului de date. Aspectul fizic al tipului de date este implementat folosind structura de date. Diferite tipuri de structuri de date sunt utilizate pentru diferite tipuri de aplicații; unii sunt specializati in anumite sarcini.
Structura datelor este o colecție de valori de date și relații între acestea, operațiuni și funcții aplicabile datelor. Acesta ajută la organizarea, gestionarea și stocarea datelor într-un anumit format. Astfel, utilizatorii pot avea acces ușor și pot modifica datele în mod eficient.
Structurile de date ajută la gestionarea unor cantități mari de date, cum ar fi bazele de date masive. Algoritmii eficienți sunt construiți pe baza unor structuri eficiente de date. Pe lângă stocarea eficientă, structurile de date sunt responsabile și pentru recuperarea eficientă a informațiilor din memoria stocată. Include o matrice, listă legată, indicator, căutare, stivă, grafic, coadă, structură, programe, sortare și așa mai departe.
Articolul acoperă conceptul de căutare în structura datelor și metodele sale. Două exemple de algoritmi sunt explicate în detaliu pentru a înțelege clar conceptul. Pentru a dobândi mai multe cunoștințe, abilități și expertiză, sunt disponibile cursuri online despre structura datelor, menționate la sfârșitul articolului.
Ce este căutarea în structura datelor?
Procesul de găsire a informațiilor dorite din setul de elemente stocate sub formă de elemente în memoria computerului este denumit „căutare în structura datelor”. Aceste seturi de articole sunt sub diferite forme, cum ar fi o matrice, un arbore, un grafic sau o listă legată. O altă modalitate de definire a căutării în structura de date este prin localizarea elementului dorit de caracteristici specifice într-o colecție de articole.
Metode de căutare
Căutarea în structura de date se poate face prin implementarea algoritmilor de căutare pentru a verifica sau a prelua un element din orice formă de structură de date stocată. Acești algoritmi sunt clasificați în funcție de tipul lor de operație de căutare, cum ar fi:
- Căutare secvenţială
Matricea sau lista de elemente este parcursă secvenţial în timp ce se verifică fiecare componentă a setului.
De exemplu, Căutare liniară.
- Căutare interval
În căutarea pe intervale sunt incluși algoritmi concepuți explicit pentru căutarea în structuri de date sortate. Eficiența acestor algoritmi este mult mai bună decât algoritmii de căutare liniară.
De exemplu, căutare binară, căutare logaritmică.
Aceste metode sunt examinate pe baza timpului necesar unui algoritm pentru a căuta un element care se potrivește cu elementul de căutare din colecțiile de date și sunt date de:
- Cel mai bun timp posibil
- Timpul mediu
- Cel mai rău caz
Preocupările principale sunt legate de timpii din cel mai rău caz care conduc la predicții garantate ale performanței algoritmului și sunt, de asemenea, ușor de calculat în comparație cu timpii medii.
Pentru a ilustra exemple și concepte din acest articol, sunt luate în considerare „n” elemente din colectarea de date în orice format de date. Operațiile dominante sunt folosite pentru a simplifica analiza și compararea algoritmilor. Pentru căutarea într-o structură de date, o comparație este o operație dominantă, care este notă cu O() și pronunțată ca „big-Oh” sau „Oh”.
Există numeroși algoritmi de căutare într-o structură de date, cum ar fi căutarea liniară, căutarea binară, căutarea prin interpolare, căutarea prin salt, căutarea exponențială, căutarea Fibonacci, căutarea sublistă, căutarea binară omniprezentă, căutarea binară nelimitată, funcția recursivă pentru căutarea subșirurilor și programul recursiv pentru a căuta un element liniar în tabloul dat. Articolul se limitează la algoritmii de căutare liniară și binar și la principiile lor de lucru.
Să obținem o perspectivă detaliată asupra căutării liniare și a căutării binare în structura de date.
Căutare liniară
Algoritmul de căutare liniară caută toate elementele din matrice secvenţial. Cel mai bun timp de execuție al său este unul, în timp ce cel mai prost timp de execuție este n, unde n este numărul total de elemente din matricea de căutare.
Este cel mai simplu algoritm de căutare din structura datelor și verifică fiecare articol din setul de elemente până când se potrivește cu elementul de căutare până la sfârșitul colectării datelor. Când datele nu sunt sortate, se preferă un algoritm de căutare liniar.
Căutarea liniară are unele complexități, după cum se arată mai jos:
- Complexitatea spațială
Complexitatea spațiului pentru căutarea liniară este O(n), deoarece nu utilizează niciun spațiu suplimentar unde n este numărul de elemente dintr-o matrice.
- Complexitatea timpului
* Complexitatea în cel mai bun caz = O(1) apare atunci când elementul de căutare este prezent la primul element din tabloul de căutare.
*Complexitatea în cel mai rău caz = O(n) apare atunci când elementul de căutare nu este prezent în setul de elemente sau în matrice.
* Complexitatea medie = O(n) se referă atunci când elementul este prezent undeva în matricea de căutare.
Exemplu,
Să luăm o serie de elemente după cum este prezentat mai jos:
45, 78, 12, 67, 08, 51, 39, 26
Pentru a găsi „51” într-o matrice de 8 elemente prezentată mai sus, un algoritm de căutare liniară va verifica fiecare element secvenţial până când indicatorul său indică 51 în spaţiul de memorie. Este nevoie de timp O(6) pentru a găsi 51 într-o matrice. Pentru a găsi 12, în tabloul de mai sus, este nevoie de O(3), în timp ce, pentru 26, este nevoie de timp O(8).
Căutare binară
Acest algoritm găsește elemente specifice comparând elementele cele mai medii din colectarea de date. Când apare o potrivire, returnează indexul articolului. Când elementul din mijloc este mai mare decât elementul, acesta caută un element central al sub-matricei din stânga. În schimb, dacă elementul din mijloc este mai mic decât elementul de căutare, acesta explorează mijlocul elementului din submatricea din dreapta. Continuă să caute un articol până când îl găsește sau până când dimensiunea sub-matrice devine zero.
Căutarea binară necesită ordine sortată a elementelor. Este mai rapid decât un algoritm de căutare liniară. Funcționează pe principiul împărți și cucerește.
Complexitatea timpului de rulare = O(log n)
Algoritmul de căutare binar are complexități după cum se arată mai jos:
- Complexitatea în cel mai rău caz = O (n log n)
- Complexitate medie = O (n log n)
- Cel mai bun caz de complexitate = O (1)
Exemplu,
Să luăm un algoritm sortat de 08 elemente:
08, 12, 26, 39, 45, 51, 67, 78
Pentru a găsi 51 într-o matrice a elementelor de mai sus,
Algoritmul va împărți o matrice în două matrice, 08, 12, 26, 39 și 45, 51, 67, 78
Deoarece 51 este mai mare decât 39, va începe să caute elemente din partea dreaptă a matricei.
Îl va împărți în două, cum ar fi 45, 51 și 67, 78
Deoarece 51 este mai mic decât 67, va începe căutarea la stânga acelui sub-matrice.
Acest subbary este din nou împărțit în două, ca 45 și 51.
Deoarece 51 este numărul care se potrivește cu elementul de căutare, va returna numărul său de index al acelui element din matrice.
Se va concluziona că elementul de căutare 51 este situat la a 6-a poziţie într-o matrice.
Căutarea binară reduce timpul la jumătate, deoarece numărul de comparații este redus semnificativ decât algoritmul de căutare liniară.
Citiți: Tipuri de structuri de date în Python
Căutare prin interpolare
Este o variantă îmbunătățită a algoritmului de căutare binar și funcționează pe poziția de sondare a elementului de căutare. Similar cu algoritmii de căutare binari, funcționează eficient doar cu colectarea de date sortată.
Cel mai prost timp de execuție = O(n)
Când locația elementului țintă este cunoscută în colectarea de date, se utilizează o căutare prin interpolare. Pentru a găsi un număr în agenda telefonică, dacă doriți să căutați numărul de telefon al Monicăi, în loc să folosiți căutarea liniară sau binară, puteți căuta direct în spațiul de stocare în memorie unde numele încep de la „M”.
Concluzie
Căutarea în structurile de date se referă la găsirea unui element dat în matricea de „n” elemente. Există două categorii, adică. Căutare secvenţială şi căutare pe intervale în căutare. Aproape toți algoritmii de căutare se bazează pe una dintre aceste două categorii. Căutările liniare și binare sunt cei doi algoritmi simpli și ușor de implementat în care binarul funcționează mai rapid decât algoritmii liniari.
Deși căutarea liniară este cea mai simplă, verifică fiecare element până când găsește o potrivire cu elementul de căutare, astfel eficient atunci când colectarea datelor nu este sortată corect. Dar, dacă colectarea datelor este sortată și lungimea unei matrice este considerabilă, atunci căutarea binară este mai rapidă.
Structura datelor este o parte esențială a programării computerelor în timp ce se ocupă cu seturile de date. Programatorii și dezvoltatorii trebuie să continue să se actualizeze și să se perfecționeze cu noțiuni de bază și actualizări ale tehnicilor de programare a computerelor. Programatorii care se ocupă de structura datelor ar trebui să opteze des pentru cursuri.
Dacă sunteți curios să aflați mai multe despre știința datelor, consultați programul Executive PG în știința datelor de la IIIT-B și upGrad, care este creat pentru profesioniști care lucrează și oferă peste 10 studii de caz și proiecte, ateliere practice practice, mentorat cu experți din industrie, 1-la-1 cu mentori din industrie, peste 400 de ore de învățare și asistență profesională cu firme de top.
