Înainte de a înțelege diferențele dintre căutarea liniară și cea binară, ar trebui să cunoaștem separat căutarea liniară și căutarea binară.

Ce este o căutare liniară?

O căutare liniară este cunoscută și sub numele de căutare secvențială care scanează pur și simplu fiecare element la un moment dat. Să presupunem că vrem să căutăm un element într-o matrice sau listă; pur și simplu îi calculăm lungimea și nu sărim la niciun element.

Să luăm în considerare un exemplu simplu.

Să presupunem că avem o matrice de 10 elemente așa cum se arată în figura de mai jos:

Figura de mai sus arată o matrice de tip de caracter având 10 valori. Dacă vrem să căutăm „E”, atunci căutarea începe de la 0^thelement și scanează fiecare element până când elementul, adică „E” nu este găsit. Nu putem sări direct de la 0^thelement la 4^thelement, adică fiecare element este scanat unul câte unul până când elementul nu este găsit.

Complexitatea căutării liniare

Ca căutare liniară scanează fiecare element unul câte unul până când elementul nu este găsit. Dacă numărul de elemente crește, crește și numărul de elemente de scanat. Putem spune că timpul necesar pentru căutarea elementelor este proporțional cu numărul de elemente . Prin urmare, complexitatea în cel mai rău caz este O(n)

Ce este o căutare binară?

O căutare binară este o căutare în care elementul din mijloc este calculat pentru a verifica dacă este mai mic sau mai mare decât elementul care urmează să fie căutat. Principalul avantaj al utilizării căutării binare este că nu scanează fiecare element din listă. În loc să scaneze fiecare element, efectuează căutarea în jumătatea listei. Deci, căutarea binară durează mai puțin timp pentru a căuta un element în comparație cu o căutare liniară.

Alesul condiția prealabilă a căutării binare este că o matrice ar trebui să fie în ordine sortată, în timp ce căutarea liniară funcționează atât pe un tablou sortat, cât și pe cel nesortat. Algoritmul de căutare binar se bazează pe tehnica divide and conquer, ceea ce înseamnă că va împărți matricea în mod recursiv.

Există trei cazuri utilizate în căutarea binară:

Cazul 1: date

Cazul 2: date>a[mid] apoi dreapta=mid-1

Cazul 3: data = a[mid] // elementul este găsit

În cazul de mai sus, ' A ' este numele matricei, mijlocul este indicele elementului calculat recursiv, date este elementul care trebuie căutat, stânga denotă elementul din stânga al tabloului și dreapta denotă elementul care apare în partea dreaptă a matricei.

Să înțelegem funcționarea căutării binare printr-un exemplu.

Să presupunem că avem o matrice cu dimensiunea 10 care este indexată de la 0 la 9, așa cum se arată în figura de mai jos:

Vrem să căutăm 70 de elemente din matricea de mai sus.

Pasul 1: Mai întâi, calculăm elementul mijlociu al unui tablou. Luăm în considerare două variabile, adică stânga și dreapta. Inițial, stânga =0 și dreapta=9 așa cum se arată în figura de mai jos:

Valoarea elementului din mijloc poate fi calculată ca:

Prin urmare, mid = 4 și a[mid] = 50. Elementul care trebuie căutat este 70, deci a[mid] nu este egal cu datele. Cazul 2 este satisfăcut, adică data>a[mid].

Pasul 2: Ca date>a[mid], deci valoarea stângă este incrementată cu mijlocul+1, adică stânga=mijlocul+1. Valoarea lui mid este 4, deci valoarea stângă devine 5. Acum, avem un subbary așa cum se arată în figura de mai jos:

Acum, din nou, valoarea medie este calculată utilizând formula de mai sus, iar valoarea medie devine 7. Acum, mijlocul poate fi reprezentat ca:

În figura de mai sus, putem observa că a[mid]>data, deci din nou, valoarea lui mid va fi calculată în pasul următor.

Pasul 3: Ca [mid]>data, valoarea dreptei este decrementată la jumătatea lui 1. Valoarea lui mid este 7, deci valoarea lui right devine 6. Matricea poate fi reprezentată ca:

Valoarea mid va fi calculată din nou. Valorile stânga și dreapta sunt 5 și, respectiv, 6. Prin urmare, valoarea lui mid este 5. Acum mijlocul poate fi reprezentat într-o matrice, așa cum se arată mai jos:

În figura de mai sus, putem observa că un[mid]

Pasul 4: Ca [mijloc]

Acum valoarea lui mid este calculată din nou utilizând formula despre care am discutat deja. Valorile stânga și dreapta sunt 6 și, respectiv, 6, astfel încât valoarea mid devine 6, așa cum se arată în figura de mai jos:

Putem observa în figura de mai sus că a[mid]=data. Prin urmare, căutarea este finalizată, iar elementul este găsit cu succes.

Diferențele dintre căutarea liniară și căutarea binară

Următoarele sunt diferențele dintre căutarea liniară și căutarea binară:

Descriere

Căutarea liniară este o căutare care găsește un element în listă căutând elementul secvenţial până când elementul este găsit în listă. Pe de altă parte, o căutare binară este o căutare care găsește recursiv elementul din mijloc în listă până când elementul din mijloc este potrivit cu un element căutat.

Funcționează ambele căutări

Căutarea liniară începe căutarea de la primul element și scanează câte un element fără a trece la următorul element. Pe de altă parte, căutarea binară împarte matricea în jumătate calculând elementul de mijloc al unei matrice.

Implementarea

Căutarea liniară poate fi implementată pe orice structură de date liniară, cum ar fi vector, listă cu legături unice, listă dublu legată. În schimb, căutarea binară poate fi implementată pe acele structuri de date cu traversare în două sensuri, adică traversare înainte și înapoi.

Complexitate

Căutarea liniară este ușor de utilizat, sau putem spune că este mai puțin complexă deoarece elementele pentru o căutare liniară pot fi aranjate în orice ordine, în timp ce într-o căutare binară, elementele trebuie aranjate într-o anumită ordine.

Elemente sortate

Elementele pentru o căutare liniară pot fi aranjate în ordine aleatorie. Nu este obligatoriu în căutarea liniară ca elementele să fie aranjate într-o ordine sortată. Pe de altă parte, într-o căutare binară, elementele trebuie aranjate în ordine sortată. Acesta poate fi aranjat fie în ordine crescătoare, fie în ordine descrescătoare și, în consecință, algoritmul va fi schimbat. Deoarece căutarea binară folosește o matrice sortată, este necesar să inserați elementul în locul potrivit. În schimb, căutarea liniară nu are nevoie de o matrice sortată, astfel încât noul element poate fi introdus cu ușurință la sfârșitul matricei.

Abordare

Căutarea liniară folosește o abordare iterativă pentru a găsi elementul, deci este cunoscută și ca abordare secvențială. În schimb, căutarea binară calculează elementul de mijloc al matricei, deci folosește abordarea împărți și cuceri.

Set de date

coduri de eroare linux

Căutarea liniară nu este potrivită pentru setul mare de date. Dacă dorim să căutăm elementul, care este ultimul element al matricei, o căutare liniară va începe căutarea de la primul element și continuă până la ultimul element, astfel încât timpul necesar pentru a căuta elementul ar fi mare. Pe de altă parte, căutarea binară este potrivită pentru un set mare de date, deoarece durează mai puțin timp.

Viteză

Dacă setul de date este mare în căutarea liniară, atunci costul de calcul ar fi mare, iar viteza devine lentă. Dacă setul de date este mare în căutarea binară, atunci costul de calcul ar fi mai mic în comparație cu o căutare liniară, iar viteza devine rapidă.

Dimensiuni

Căutarea liniară poate fi utilizată atât pe o matrice unică, cât și pe multidimensională, în timp ce căutarea binară poate fi implementată doar pe o matrice unidimensională.

Eficienţă

Căutarea liniară este mai puțin eficientă atunci când luăm în considerare seturile mari de date. Căutarea binară este mai eficientă decât căutarea liniară în cazul seturilor mari de date.

Să ne uităm la diferențele într-o formă tabelară.