Implementarea căutării binare într-un vector

Să vedem cum gândim căutarea binară pe un vector sortat. Da, JavaScript oferă deja metode pentru a determina dacă un anumit element se găsește într-un vector și, dacă da, poziția sa (cum fac multe limbaje de programare). Dar aici vrem să o implementăm noi înșine, pentru a înțelege cum poți pune în aplicare astfel de metode. Iată un vector JavaScript cu primele 25 de numere prime, în ordine:

Să presupunem că vrem să ştim dacă numărul 67 este prim. Dacă 67 se găsește în vector, atunci el este număr prim.

De asemenea, am dori să știm câte numere prime sunt mai mici decât 67. Dacă găsim poziţia numărului 67 în vector, o putem folosi pentru a afla câte numere prime mai mici există.

Poziția unui element într-un vector este cunoscută ca indcele său. Indicii vectorului pornesc de la 0 și cresc. Dacă un element are indicele 0, atunci acesta este primul element din vector. Dacă un element are indicele 3, atunci înaintea lui se găsesc 3 elemente.

Uitându-ne la exemplul de mai jos, putem citi vectorul de numere prime de la stânga la dreapta, unu câte unu, până când găsim numărul 67 (în caseta roz) și vedem că are indicele 18. Parcurgerea numerelor în această ordine se numește căutare liniară.

Odată ce ştim că numărul prim 67 are indicele 18, putem înțelege că este un număr prim. De asemenea, putem vedea rapid faptul că 18 elemente vin înainte de 67 în vector, ceea ce înseamnă că există 18 numere prime mai mici decât 67.

Ai văzut câți pași au fost făcuți? O căutare binară ar putea fi mai eficientă. Deoarece vectorul prime conţine 25 de numere, indicii sunt din intervalul de valori 0 - 24. Folosind pseudocodul de mai devreme, începem prin a atribui valorile min = 0 și max = 24. Prin urmare, prima încercare în căutarea binară ar fi la poziția 12 (care este (0 + 24) / 2). Este prime[12] egal cu 67? Nu, primes[12] este 41.

Este indicele pe care îl căutăm mai mare sau mai mic decât 12? Deoarece valorile din vector sunt în ordine crescătoare, iar 41 < 67, valoarea 67 trebuie să fie în dreapta indicelui 12 . Cu alte cuvinte, indicele elementului pe care încercăm să-l ghicim ar trebui să fie mai mare decât 12. Actualizăm valoarea lui min la 12 + 1, adică 13, și lăsăm max neschimbat, egal cu 24.

Care este următorul index de încercat? Media numerelor 13 și 24 este 18,5, pe care o rotunjim la 18, deoarece un indice într-un vector trebuie să fie un număr întreg. Găsim că prime[18] este 67.

Algoritmul binar de căutare se oprește în acest moment, deoarece am găsit răspunsul. A fost nevoie de doar două încercări, în loc de cele 19 pe care le-ar fi avut căutarea liniară. Poți trece prin asta din nou, în vizualizarea de mai jos:

Tocmai am descris, în limba română, algoritmul binar de căutare, luând un exemplu. Este o modalitate de a face asta, dar o explicaţie în limbajul uman poate varia în ceea ce priveşte calitatea. Poate fi prea scurtă sau prea lungă, dar, cel mai important, nu este întotdeauna atât de precisă pe cât ar trebui. Am putea să arătăm direct căutarea binară într-un limbaj de programare cum ar fi JavaScript sau Python, dar programele conțin multe detalii - din cauza cerințelor impuse de limbajul de programare, sau pentru că programele trebuie să gestioneze erori cauzate de date eronate, eroare de utilizator, sau defecțiuni de sistem - iar acestea pot face dificilă înțelegerea algoritmului de la baza codului. De aceea, preferăm să descriem algoritmul în ceva numit pseudocod, care folosește limba română, dar cu caracteristici pe care le au limbajele de programare.

Iată pseudocodul pentru căutarea binară, modificat pentru căutarea într-un vector. Datele de intrare sunt vectorul, pe care îl numim vector, numărul de elemente n din vector, precum şi ţinta, adică numărul căutat. Ca dată de ieșire avem poziția din vector a țintei:

Vom alterna între română, pseudocod şi JavaScript în aceste tutoriale, în funcţie de situaţie. Ca programator, ar trebui să înveți să înțelegi limbajul pseudocod și să îl poți transforma în limbajul ales de tine - deci chiar dacă folosim JavaScript aici, ar trebui să fie simplu pentru tine să implementezi pseudocodul folosind alte limbaje.

Cum am transforma acel pseudocod într-un program JavaScript? Ar trebui să creăm o funcție, deoarece scriem un cod care acceptă o intrare și returnează o ieșire, și vrem ca acel cod să fie reutilizabil pentru diferite intrări. Parametrii funcției — să-i spunem binarySearch— vor fi vectorul și valoarea țintă, iar valoarea returnată a funcției va fi indicele poziției pe care a fost găsită valoarea țintă.

Acum, să mergem în corpul funcției și să vedem cum implementăm. Pasul 6 spune să ne întoarcem la pasul 2. Asta pare a fi o buclă. Să fie for sau while? Dacă am vrea să folosim for, am putea, dar indicii încercați în căutarea binară nu sunt în ordine secvențială, cea care ar fi mai convenabilă pentru o repetiție de tip for. Mai întâi am putea încerca indicele 12, apoi 18, așa cum obținem din calcule. Așadar, repetiția while este o alegere mai bună.

De asemenea, lipsește un pas important în pseudocod, pas care nu este relevant pentru jocul de ghicit, dar contează pentru căutarea binară într-un vector. Ce ar trebui să se întâmple dacă numărul pe care îl căutăm nu este în vector? Hai să ne dăm seama ce indidice ar trebui să returneze funcţia binarySearch, în acest caz. Ar trebui să fie un număr care nu poate reprezenta indice în vector. Vom folosi -1, deoarece acesta nu poate fi indice în nici un vector. (De fapt, orice număr negativ ar merge.)

Numărul ţintă nu este în vector dacă nu mai există încercări. În exemplul nostru, presupunem că numărul pe care îl căutăm în vectorul prime este 10. În acest caz, 10 ar fi între valorile 7 şi 11, care au indicii 3, respectiv 4. Dacă urmărim valorile indicilor lui min și max pentru care se execută funcția binarySearch, observăm că ajung în cele din urmă ca min să fie egal cu 3 şi max egal cu 4. Următoarea încercare are indicele 3 (de la (3 + 4) / 2 este egal cu 3,5 și rotunjim prin lipsă), iar prime[3] este mai mic decât 10, deci min devine 4. Pentru că atât min cât şi max sunt egale cu 4, trebuie să încercăm indicele 4, iar prime[4] este mai mare decât 10. Acum max devine 3. Ce înseamnă că min egal cu 4 şi max egal cu 3? Înseamnă că singurele încercări posibile sunt cel puțin 4 și cel mult 3. Nu există astfel de numere! În acest moment, putem concluziona că numărul ţintă, 10, nu este în vectorul prime, iar funcţia binarySearch ar returna -1. În general, odată ce max devine strict mai mic decât min, ştim că numărul ţintă nu este în vectorul sortat. Aici este modificat pseudocodul pentru căutarea binară care se ocupă de cazul în care numărul țintă nu este prezent:

După ce am trecut prin pseudocod împreună, vei încerca să implementezi singur căutarea binară. Poți să te uiţi din nou la pseudocod - de fapt, este indicat, deoarece vei înţelege mai bine ce înseamnă să transformi pseudocodul într-un program.

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ă de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.