Un joc de ghicit

Hai să jucăm un joculeț în care vei vedea că diferiți algoritmi pot avea eficiență diferită pentru aceeași problemă. Calculatorul va selecta aleatoriu un număr întreg cuprins între 1 și 15. Vei încerca să spui numere până când găsești numărul ales de calculator; după fiecare număr pe care îl spui, calculatorul îți precizează dacă numărul tău este prea mare sau prea mic:

Odată ce găsești numărul, reflectează asupra tehnicii pe care ai folosit-o atunci când ai decis cum încerci să ghicești numărul.

Poate ai încercat 1, apoi 2, apoi 3, apoi 4 şi aşa mai departe, până când ai ghicit numărul corect. Numim această tehnică căutare liniară, pentru că iei toate numerele ca și cum ar fi aliniate. Ar funcţiona. Dar care este cel mai mare număr de presupuneri de care ai avea nevoie? În cazul în care calculatorul selectează 15, ai avea nevoie de 15 presupuneri. Şi iarăşi, ai putea fi foarte norocos, atunci când calculatorul selectează 1 pentru că vei ghici numărul de la prima presupunere. Dar în medie? Este la fel de probabil să fie selectat oricare număr cuprins între 1 și 15, așa încât, în medie, vei avea nevoie de 8 presupuneri.

Dar ai putea face ceva mai eficient decât să iei numerele 1, 2, 3, 4, …, în această ordine? Deoarece calculatorul vă spune dacă o presupunere este prea mică, prea mare sau corectă, poți începe cu numărul 8. Dacă numărul selectat de calculator este mai mic decât 8, atunci 8 este prea mare, deci poți elimina toate numerele de la 8 la 15. Dacă numărul selectat de calculator este mai mare de 8, atunci poți elimina numerele de la 1 până la 8. Oricum, poţi elimina jumătate din numere. La următoarea presupunere, elimini jumătate din numerele rămase. Continui, eliminând întotdeauna jumătate din numerele rămase.

Numim această tehnică de înjumătățire căutare binară și oricare ar fi numărul cuprins între 1 și 15 pe care l-a selectat calculatorul, ar trebui să poți găsi numărul în cel mult 4 presupuneri, cu ajutorul acestei tehnici.

Acum, să încercăm pentru un număr cuprins între 1 și 300. Nu ar trebui să ai nevoie de mai mult de 9 presupuneri.

Câte încercări ți-a luat să ghicești numărul de data aceasta? De ce nu ar trebui să ai nevoie de mai mult de 9 presupuneri? (Poți să te gândești la o explicaţie matematică)?

Ne vom întoarce la căutarea binară și vom vedea cum poate fi folosită pentru a căuta eficient un element într-un vector JavaScript. Dar mai întâi, hai să ne uităm la un algoritm pentru o problemă mai complicată.

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.