Algoritm de căutare binar: funcție, beneficii, complexitate timp și spațiu

Introducere

În orice sistem de calcul, căutarea este una dintre cele mai critice funcționalități de dezvoltat. Tehnicile de căutare sunt utilizate în regăsirea fișierelor, indexare și multe alte aplicații. Există multe tehnici de căutare disponibile. Una dintre ele este tehnica de căutare binară.

Un algoritm de căutare binar funcționează pe ideea de a neglija jumătate din listă la fiecare iterație. Continuă să împartă lista până când găsește valoarea pe care o caută într-o listă dată. Un algoritm de căutare binar este o actualizare rapidă la un algoritm simplu de căutare liniară.

Nu este necesară experiență de codare. Suport în carieră la 360°. Diploma PG în Machine Learning și AI de la IIIT-B și upGrad.

Funcționarea unui algoritm de căutare binar

Primul lucru de remarcat este că un algoritm de căutare binar funcționează întotdeauna pe o listă sortată. Prin urmare, primul pas logic este sortarea listei furnizate. După sortare, mediana listei este verificată cu valoarea dorită.

• Dacă valoarea dorită este egală cu valoarea indicelui central, atunci indicele este returnat ca răspuns.

• Dacă valoarea țintă este mai mică decât valoarea indexului central al listei, atunci partea dreaptă a listei este ignorată.

• Dacă valoarea dorită este mai mare decât valoarea indexului central, atunci jumătatea din stânga este aruncată.

• Procesul este apoi repetat pe liste scurtate până când este găsită valoarea țintă.

Exemplul #1

Să ne uităm la algoritm cu un exemplu. Să presupunem că există o listă cu următoarele numere:

1, 15, 23, 7, 6, 14, 8, 3, 27

Să luăm valoarea dorită ca fiind 27. Numărul total de elemente din listă este 9.

Primul pas este sortarea listei. După sortare, lista ar arăta cam așa:

1, 3, 6, 7, 8, 14, 15, 23, 27

Întrucât numărul de elemente din listă este nouă, indicele central ar fi la cinci. Valoarea de la indicele cinci este 8. Valoarea dorită, 27, este comparată cu valoarea 8. În primul rând, verificați dacă valoarea este egală cu 8 sau nu. Dacă da, întoarceți indexul și ieșiți.

Deoarece 27 este mai mare decât 8, am ignora partea stângă și am traversa doar partea dreaptă a listei. Noua listă de parcurs este:

14, 15, 23, 27

Notă: În practică, lista nu este trunchiată. Doar observația este restrânsă. Deci, „noua listă” nu trebuie confundată cu crearea unei noi liste sau scurtarea celei originale. Deși ar putea fi implementat cu o nouă listă, există două probleme. În primul rând, va exista o memorie. Fiecare listă nouă va crește complexitatea spațiului. Și în al doilea rând, indicii originali trebuie urmăriți la fiecare iterație.

Noul indice central poate fi luat ca al doilea sau al treilea element, în funcție de implementare. Aici, vom considera al treilea element ca fiind central. Valoarea 23 este comparată cu valoarea 27. Deoarece valoarea este mai mare decât valoarea centrală, vom arunca jumătatea stângă.

Lista de parcurs este:

27

Deoarece lista conține doar un singur element, acesta este considerat elementul central. Prin urmare, comparăm valoarea dorită cu 27. Pe măsură ce se potrivesc, returnăm valoarea indexului de 27 în lista originală.

Exemplul #2

În aceeași listă, să presupunem că valoarea dorită este 2.

În primul rând, valoarea centrală opt este comparată cu 2. Deoarece valoarea dorită este mai mică decât valoarea centrală, ne îngustăm atenția către partea stângă a listei.

Noua traversare va consta din:

1, 3, 6, 7

Să luăm elementul central drept al doilea element. Valoarea dorită doi este comparată cu 3. Deoarece valoarea este încă mai mică, restrângem din nou focalizarea în partea stângă a listei.

Noua traversare va consta din:

1

Deoarece lista de parcurgere are un singur element, valoarea este direct comparată cu elementul rămas. Vedem că valorile nu se potrivesc. Prin urmare, ieșim din buclă cu un mesaj de eroare: v alue not found .

Certificare avansată în știința datelor, peste 250 de parteneri de angajare, peste 300 de ore de învățare, 0% EMI

Complexitatea timpului și spațiului

Complexitatea temporală a algoritmului de căutare binar este O(log n). Complexitatea de timp în cel mai bun caz ar fi O(1) atunci când indicele central s-ar potrivi direct cu valoarea dorită. Scenariul cel mai rău ar putea fi valorile de la oricare dintre extremitățile listei sau valorile care nu se află în listă.

Complexitatea spațială a algoritmului de căutare binar depinde de implementarea algoritmului. Există două moduri de implementare:

1. Metoda iterativă
2. Metoda recursiva

Ambele metode sunt aproape aceleași, cu două diferențe în implementare. În primul rând, nu există nicio buclă în metoda recursivă. În al doilea rând, în loc să treacă noile valori la următoarea iterație a buclei, le trece la următoarea recursivitate. În metoda iterativă, iterațiile pot fi controlate prin condițiile de buclă, în timp ce în metoda recursivă, maximul și minimul sunt folosite ca condiție la limită.

În metoda iterativă, complexitatea spațiului ar fi O(1). În timp ce în metoda recursivă, complexitatea spațiului ar fi O(log n).

Beneficii

• Un algoritm de căutare binar este un algoritm de căutare destul de simplu de implementat.

• Este o îmbunătățire semnificativă față de căutarea liniară și funcționează aproape la fel în comparație cu unii dintre algoritmii de căutare mai greu de implementat.

• Algoritmul de căutare binar împarte lista în jumătate la fiecare iterație, mai degrabă decât să parcurgă lista în mod secvențial. Pe liste mari, această metodă poate fi cu adevărat utilă.

Checkout: Clasificare în arborele de decizie: tot ce trebuie să știți

Concluzie

Un algoritm de căutare binar este un algoritm utilizat pe scară largă în domeniul computațional. Este un algoritm de căutare gras și precis, care poate funcționa bine atât pe seturi de date mari, cât și pe cele mici. Un algoritm de căutare binar este un algoritm simplu și de încredere de implementat. Odată cu analiza timpului și spațiului, beneficiile utilizării acestei tehnici sunt evidente.

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.