If you're seeing this message, it means we're having trouble loading external resources on our website.

Dacă sunteţi în spatele unui filtru de web, vă rugăm să vă asiguraţi că domeniile *. kastatic.org şi *. kasandbox.org sunt deblocate.

Conţinutul principal

Căutare binară

Căutarea binară este un algoritm eficient pentru găsirea unui articol dintr-o listă sortată de articole. Funcționează prin înjumătățirea repetată a listei care ar putea conține obiectul, până când ajungem la doar un singur articol. Am folosit căutarea binară în joc de ghicit din tutorialul introductiv.
Una dintre cele mai întâlnite situații de utilizare a căutării binare este cea a căutării unui element într-un vector. De exemplu, catalogul de stele Tycho-2 conține informații despre cele mai strălucitoare 2,539 913 stele din galaxia noastră. Să presupunem că dorești să cauți în catalog o anumită stea, pe baza numelui stelei. Dacă programul ar examina fiecare stea din catalog începând cu prima, algoritm numit căutare liniară, computerul ar putea fi nevoit să examineze toate cele 2 539 913 stele pentru a găsi steaua pe care o cauţi, în cazul cel mai defavorabil. În cazul în care catalogul este sortat alfabetic după nume de stele, căutarea binară nu ar trebui să examineze mai mult de 22 de stele, chiar și în cel mai defavorabil caz.
Următoarele câteva articole discută despre cum să descrii algoritmul cu atenție, cum să implementezi algoritmul în JavaScript și cum să analizezi eficiența.

Descrierea căutării binare

Când descriem un algoritm pe care îl explicăm unei persoane, o descriere incompletă este adesea suficient de bună. Unele detalii pot fi omise dintr-o reţetă pentru o prăjitură; reţeta presupune că ştii cum să deschizi frigiderul, pentru a scoate ouăle şi că ştii cum să spargi ouăle. Oamenii ar putea ști intuitiv cum să completeze detaliile lipsă, dar programele de calculator nu o fac. De aceea, trebuie să descriem complet algoritmii pentru calculator.
Pentru a implementa un algoritm într-un limbaj de programare, va trebui să înțelegi algoritmul în cele mai mici detalii. Care sunt datele de intrare ale problemei? Care sunt datele de ieșire? Ce variabile ar trebui să fie create și ce valori inițiale ar trebui să aibă acestea? Ce pași intermediari ar trebui parcurși pentru a calcula alte valori și pentru a calcula în cele din urmă datele de ieșire? Repetă acești pași instrucțiuni care pot fi scrise într-o formă simplificată folosind o buclă (structură repetitivă)?
Să privim cu atenție cum putem descrie căutarea binară. Ideea principală a căutării binare este să ținem evidența intervalului curent cu valori posibile. Să zicem că mă gândesc la un număr între unu și 100, exact ca la jocul de ghicit. Dacă ai încercat deja 25 şi ți-am spus că numărul meu este mai mare, ai ai încercat deja 81 şi ți-am spus că numărul meu este mai mic, apoi numerele cuprinse între 26 şi 80 sunt singurele estimări rezonabile. Aici, secţiunea roşie de pe axa numerelor conţine valorile rezonabile, iar secţiunea neagră le arată pe cele pe care le-am exclus:
La fiecare rând, alegem o valoare care împarte setul de valori posibile în două intervale de aproximativ aceeaşi dimensiune. Dacă bănuiala ta nu e corectă, atunci îți spun dacă e prea mare sau prea mică şi poţi elimina aproape jumătate din valorile posibile. De exemplu, dacă intervalul curent conține valorile între 26 şi 80, ai putea încerca punctul de la jumătate, (26+80)/2, adică 53. Dacă îți spun că numărul 53 este prea mare, poți elimina toate numerele de la 53 la 80, păstrându-le pe cele cuprinse între 26 şi 52 și reducând la jumătate lungimea intervalului.
Pentru jocul de ghicit, putem ține evidența intervalului de valori posibile folosind câteva variabile. Fie min variabila care reprezintă valoarea minimă posibilă curentă, pentru această rundă, iar max valoarea maximă curentă. Ca dată de intrare a problemei avem numărul n, cel mai mare număr posibil la care se poate gândi adversarul tău. Presupunem că cel mai mic număr posibil este unu, dar ar fi ușor de modificat algoritmul astfel încât cel mai mic număr posibil să reprezinte o a doua dată de intrare.
Iată o descriere pas cu pas pentru utilizarea căutării binare în jocul de ghicit:
  1. Fie min=1 și max=n
  2. Încearcă media dintre max și min, rotunjită la un număr întreg.
  3. Dacă ai ghicit numărul, oprește-te. L-ai găsit!
  4. Dacă valoarea este prea mică, setează min să fie cu unu mai mare decât valoarea încercată.
  5. Dacă valoarea încercată a fost prea mare, setează max să fie cu unu mai mic decât aceasta.
  6. Mergi înapoi la pasul doi.
Am putea face această descriere și mai precisă prin descrierea clară a datelor de intrare și a celor de ieșire ale algoritmului și prin clarificări legate de ce se înțelege prin instrucțiuni precum "ghicește un număr" și "oprește-te". Dar considerăm că este suficient de detaliat, deocamdată.
În continuare, vom vedea cum putem folosi căutarea binară într-un vector și vom discuta despre cum să transformăm descrierile algoritmilor într-un cod funcțional.

Acest conținut este o colaborare a profesorilor Thomas Cormen și Devin Balkcom, de la Dartmouth Computer Science, cu echipa de elaborare a curriculumului de informatică a Khan Academy. Conținutul este licențiat CC-BY-NC-SA.