Căutare liniară vs căutare binară: diferența dintre căutare liniară și căutare binară

Publicat: 2021-02-09

Cuprins

Introducere

Alocarea contigue a memoriei în limbaje de programare oferă o implementare flexibilă a stocării mai multor puncte de date. Acest lucru poate fi utilizat la apogeu dacă dorim să segregam datele și să îmbinăm toate datele similare într-o structură de date adiacentă, cum ar fi o matrice, o listă etc.

Alocarea de memorie contiguă are multe implementări în aplicațiile din lumea reală, cum ar fi un sistem de operare în computere, sisteme de gestionare a bazelor de date, etc. Această structură de date este considerată una flexibilă deoarece adăugarea unui nou punct de date la o matrice necesită doar o singură unitate de timp, de exemplu; O(1).

Dar problema apare atunci când vrem să ne uităm la o anumită intrare sau să căutăm o anumită intrare, deoarece toate aplicațiile din lumea reală se bazează pe comenzile de accesare a datelor. Și această sarcină trebuie să fie suficient de rapidă pentru a atinge viteza procesorului și a memoriei.

Există diverși algoritmi de căutare împărțiți în funcție de numărul de comparații pe care le facem pentru a căuta elementul.

Dacă comparăm fiecare punct de date din matrice pentru a căuta un element, atunci acesta este considerat o căutare secvențială. Dar dacă comparăm doar câteva elemente omitând unele dintre comparații, atunci este considerată o căutare pe intervale. Dar avem nevoie de o matrice care să fie în ordine sortată (ordine crescătoare sau descrescătoare) pentru a efectua o căutare pe interval.

Complexitatea de timp a căutării secvenţiale este liniară O(n), iar complexitatea de timp a căutării binare (un exemplu de căutare pe intervale) este O(log n). De asemenea, există și alți algoritmi de căutare precum căutarea exponențială, căutarea prin salt etc.

Dar căutarea liniară și căutarea binară sunt folosite în cea mai mare parte, unde căutarea liniară este pentru date aleatoare sau nesortate, iar căutarea binară este pentru date sortate și ordonate. Hashing este un algoritm special de căutare în care complexitatea de timp a accesării unui punct de date este O(1).

Să parcurgem mai întâi algoritmii de căutare liniară și de căutare binară și apoi să comparăm diferențele dintre căutarea liniară și căutarea binară.

Căutare liniară

După cum sa discutat deja, algoritmul de căutare liniară compară fiecare element din matrice și iată codul pentru a face asta.

clasă publică UpGrad {
 public static int căutare_liniară ( int [] arr, int n, int k){
 pentru ( int i= 0 ; i<n; i++)
 dacă (arr[i]==k)
 returnează i+ 1 ;
 întoarcere – 1 ;
 }
 public static void main (String[] args){
 int [] arr= new int []{ 1 , 2 , 5 , 6 , 3 , 8 , 9 , 9 , 0 , 13 , 45 , 65 };
 int k= 13 ;
 int n=arr.length;
 int r=linear_search(arr, n, k);
 dacă (r==- 1 )
 System.out.println( „elementul nu a fost găsit” );
 altfel
 System.out.println( „element găsit la poziția „ +r+ ”” );
 }
 }

Să parcurgem codul.

Am declarat o funcție linear_search, care așteaptă ca parametri o matrice, o cheie întreagă. Acum trebuie să trecem peste toate elementele și să comparăm dacă se potrivește cu cheia noastră de căutare, așa că am scris o buclă for care trece peste matrice, iar în interiorul ei, există o buclă if care verifică dacă numărul de la acea poziție se potrivește. cu cheia de căutare sau nu. Dacă găsim o potrivire, vom întoarce poziția. Dacă nu există un astfel de element în matrice, atunci vom returna -1 la sfârșitul funcției.

Rețineți că dacă avem mai multe apariții ale aceluiași număr, atunci vom returna poziția primei sale apariții.

Venind la metoda principală, am declarat și inițializat un tablou întreg. Apoi inițializam cheia care trebuie căutată. Aici codificăm matricea și cheia, dar le puteți schimba la intrarea utilizatorului. Acum că avem lista de elemente și cheia de căutat, se apelează metoda de căutare liniară și se notează indexul returnat. Mai târziu verificăm valoarea returnată și tipărim indexul dacă cheia există, altfel cheia de tipărire nu a fost găsită.

Căutare binară

Căutarea binară este mai optimizată decât căutarea liniară, dar matricea trebuie sortată pentru a aplica căutarea binară. Și iată codul pentru a face asta.

clasă publică UpGrad {
 public static int binary_search ( int [] arr, int k){
 int l= 0 ,h=arr.length- 1 ,mid= 0 ;
 în timp ce (l<=h){
 mijloc=l+(hl)/ 2 ;
 dacă (arr[mid]==k)
 întoarcere la mijloc+ 1 ;
 else if (arr[mid]>k)
 h=mid- 1 ;
 altfel
 l=mid+ 1 ;
 }
 întoarcere – 1 ;
 }
 public static void main (String[] args){
 int [] arr= new int []{ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 };
 int k= 8 ;
 int r=binary_search(arr,k);
 dacă (r==- 1 )
 System.out.println( „elementul nu a fost găsit” );
 altfel
 System.out.println( „element găsit la poziția „ +r+ ”” );
 }
 }

Să parcurgem codul.

Am declarat o metodă binary_search care așteaptă ca parametri o matrice întregă sortată și o cheie întreagă. Inițializam variabilele low, high, mid. Aici low, high sunt indicatorii unde low va fi la 0 index și high va fi la n index la început. Deci, cum funcționează căutarea binară?

La început, vom calcula mijlocul, scăzut și ridicat. Putem calcula mediul ca (scăzut+înalt)/2, dar uneori mare poate fi un număr mare, iar adăugarea unui nivel scăzut la mare poate duce la depășirea întregului. Deci, calcularea mediei ca și low+(high-low)/2 ar fi o modalitate optimă.

Vom compara elementul de la mijloc cu cheia de căutare și vom returna indexul dacă găsim o potrivire. În caz contrar, vom verifica dacă elementul din mijloc este mai mare decât cheia sau mai mic decât cheia. Dacă mijlocul este mai mare, atunci trebuie să verificăm doar prima jumătate a matricei, deoarece toate elementele din a doua jumătate a matricei sunt mai mari decât cheia, așa că vom actualiza valoarea maximă la mijlocul 1.

În mod similar, dacă mijlocul este mai mic decât cheia, atunci trebuie să căutăm în a doua jumătate a matricei, prin urmare actualizând valoarea scăzută la mijlocul +1. Rețineți că căutarea binară se bazează pe algoritmul de scădere și cucerire, deoarece ignorăm una dintre jumătățile matricei în fiecare iterație.

Revenind la codul nostru, am construit metoda principală. A inițializat o matrice sortată și o cheie de căutare, a efectuat un apel la căutarea binară și a tipărit rezultatele.

Acum că am parcurs algoritmii atât ai căutării liniare, cât și ai căutării binare, să comparăm ambii algoritmi.

Căutare liniară vs căutare binară

Lucru

  • Căutarea liniară iterează prin toate elementele și le compară cu cheia care trebuie căutată.
  • Căutarea binară scade în mod înțelept dimensiunea matricei care trebuie căutată și compară de fiecare dată cheia cu elementul mijlociu.

Structură de date

  • Căutarea liniară este flexibilă cu toate structurile de date, cum ar fi o matrice, o listă, o listă legată etc.
  • Căutarea binară nu poate fi efectuată pe toate structurile de date, deoarece avem nevoie de traversare multidirecțională. Deci, structurile de date precum lista unică legată nu pot fi utilizate.

Cerințe preliminare

  • Căutarea liniară poate fi efectuată pe toate tipurile de date, datele pot fi aleatorii sau sortate, algoritmul rămâne același. Deci nu este nevoie de nicio lucrare prealabilă.
  • Căutarea binară funcționează numai pe o matrice sortată. Deci sortarea unui tablou este o condiție prealabilă pentru acest algoritm.

Utilizare caz

  • Căutarea liniară este în general preferată pentru seturi de date mai mici și ordonate aleatoriu.
  • Căutarea binară este preferată pentru seturi de date comparativ mai mari și sortate.

Eficacitatea

  • Căutarea liniară este mai puțin eficientă în cazul seturilor de date mai mari.
  • Căutarea binară este mai eficientă în cazul seturilor de date mai mari.

Complexitatea timpului

  • În căutarea liniară, complexitatea în cel mai bun caz este O(1) unde elementul se găsește la primul indice. Complexitatea în cel mai rău caz este O(n) unde elementul este găsit la ultimul index sau elementul nu este prezent în matrice.
  • În căutarea binară, complexitatea în cel mai bun caz este O(1) unde elementul se găsește la indexul din mijloc. Cel mai rău caz de complexitate este O( log 2 n).

Dry Run

Să presupunem că avem o matrice de dimensiunea 10.000.

  • Într-o căutare liniară, complexitatea în cel mai bun caz este O(1) și complexitatea în cel mai rău caz este O(10000).
  • Într-o căutare binară, complexitatea în cel mai bun caz este O(1) și complexitatea în cel mai rău caz este O ( log 2 10000)=O(13,287).

Concluzie

Am înțeles importanța accesării datelor în matrice, am înțeles algoritmii de căutare liniară și de căutare binară. Am parcurs codurile căutării liniare și ale căutării binare. A comparat diferențele dintre căutarea liniară și căutarea binară, a făcut o rulare uscată pentru un exemplu de dimensiuni mari.

Acum că sunteți conștient de diferențele dintre căutarea liniară și căutarea binară, încercați să rulați ambele coduri pentru un set de date mare și să comparați timpul de execuție, începeți să explorați diferiți algoritmi de căutare și încercați să le implementați!

Dacă sunteți curios să aflați despre știința datelor, consultați Diploma 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- on-1 cu mentori din industrie, peste 400 de ore de învățare și asistență profesională cu firme de top.

Învață cursuri de știință a datelor online de la cele mai bune universități din lume. Câștigă programe Executive PG, programe avansate de certificat sau programe de master pentru a-ți accelera cariera.

Comparați căutarea liniară și căutarea binară folosind complexitatea acestora.

Căutarea binară este mai optimizată și mai eficientă decât Căutarea liniară în multe feluri, mai ales când elementele sunt în ordine sortată. Motivul se rezumă la complexitatea ambelor căutări.
Căutare liniară
1. Complexitatea timpului: O(N) - Deoarece în căutarea liniară, parcurgem tabloul pentru a verifica dacă vreun element se potrivește cu cheia. În cel mai rău caz, elementul va fi prezent la sfârșitul matricei, așa că trebuie să traversăm până la sfârșit și, prin urmare, complexitatea timpului va fi O(N) unde N este numărul total de elemente ale matricei.
2. Complexitatea spațiului: O(1) - Nu folosim niciun spațiu suplimentar, așa că complexitatea spațiului va fi O(1).
Căutare binară
1. Complexitatea timpului: O(log N) - În căutarea binară, căutarea se reduce la jumătate, deoarece trebuie doar să privim în sus la mijlocul matricei. Și ne scurtăm constant căutarea la mijlocul secțiunii în care elementul este prezent.
2. Complexitatea spațiului: O(1)
- Nu folosim niciun spațiu suplimentar, așa că complexitatea spațiului va fi O(1).

Există vreo altă metodă de a căuta un element dintr-o matrice?

Deși căutarea liniară și căutarea binară sunt adesea folosite pentru căutare, există într-adevăr o altă metodă de căutare - metoda interpolării. Este o versiune optimizată a Căutării binare în care toate elementele sunt distribuite uniform.
Ideea din spatele acestei metode este că în căutarea binară, privim întotdeauna în sus la mijlocul matricei. Dar în această metodă, căutarea poate merge în diferite locații, în funcție de locul în care se află cheia. De exemplu, dacă cheia este situată lângă ultimul element al matricei, căutarea va începe de la sfârșitul matricei.

Care sunt diferitele complexități de timp ale căutării prin interpolare?

Complexitatea de timp în cel mai rău caz a căutării prin interpolare este O(N), deoarece în cel mai rău caz, cheia va fi la sfârșitul matricei, astfel încât iteratorul trebuie să traverseze întreaga matrice.
Complexitatea medie a cazului va fi O(log(log N), deoarece elementul poate fi oriunde în matrice. Poate fi și aproape de punctul de plecare.
Complexitatea în cel mai bun caz va fi O(1), deoarece, în cel mai bun caz, cheia va fi chiar primul element al matricei.