Timpul de execuție al căutării binare

Știm că, pe un vector de $n$n elemente, căutarea liniară ar putea avea nevoie de $n$n încercări. Probabil ai intuit deja că prin căutarea binară se fac mai puţine încercări decât prin căutarea liniară. S-ar putea să fi înțeles că diferența dintre cel mai defavorabil caz pentru căutarea liniară și căutarea binară devine tot mai frapantă pe măsură ce lungimea vectorului crește. Să vedem cum analizăm numărul maxim de încercări pe care le facem cu căutarea binară.

Ideea cheie este că atunci când căutarea binară face o încercare incorectă, lungimea vectorului care conține valori rezonabile este redusă cu cel puțin jumătate. Dacă vectorul inițial are 32 de elemente, atunci o încercare incorectă îl va reduce la cel mult 16 elemente. Căutarea binară înjumătățește numărul valorilor rezonabile la fiecare încercare incorectă.

Dacă începem cu un vector de lungime 8, atunci încercările incorecte reduc numărul valorilor rezonabile la 4, apoi la 2, iar apoi la 1. Odată ce avem un singur element rezonabil, nu se mai fac alte încercări; încercarea pentru 1 element este fie corectă, fie incorectă, apoi am terminat. Deci pentru un vector de lungime 8, căutarea binară are nevoie de cel mult patru încercări.

Ce crezi că se întâmplă cu un vector de 16 elemente? Dacă ai spus că prima încercare ar elimina cel puțin 8 elemente, astfel încât cel mult 8 să rămână, înseamnă că ai înțeles ideea. Deci, pentru 16 elemente avem nevoie de cel mult cinci încercări.

De acum, probabil vezi șablonul. De fiecare dată când dublăm dimensiunea vectorului, avem nevoie de cel mult încă o încercare. Presupunem că avem nevoie de cel mult $m$m încercări pentru un vector de $n$n elemente. Apoi, pentru un vector de lungime $2n$2, n, prima încercare elimină din valorile rezonabile din vector până la un număr de $n$n valori, iar după cel mult $m$m încercări se termină, dându-ne un total de cel mult $m+1$m, plus, 1 încercări.

Să ne uităm la cazul general al unui vector de lungime $n$n. Am putea exprima numărul de încercări, în cel mai defavorabil caz, astfel: "de câte ori putem înjumătăți, începând cu $n$n, până când obținem valoarea 1, plus unu". Dar nu e convenabil să scriem așa.

Din fericire, există o funcţie matematică care înseamnă acelaşi lucru cu numărul înjumătățiri, începând de la $n$n, până când pajungem la valoarea 1: logaritm în baza 2 din $n$n. Este cel mai adesea scris ca $\log_2 n$log, start base, 2, end base, n, dar îl poți întâlni și scris ca $\lg n$\lg, n, în scrierile din informatică. Vrei să recapitulezi logaritmii? Află mai multe aici.)

Iată un tabel care conține logaritmii în baza 2 pentru diverse valori ale lui $n$n:

Putem vedea același tabel ca un grafic:

Evidențierea pentru valori mai mici ale lui n:

Funcția logaritm crește foarte lent. Logaritmii sunt funcții inverse ale exponentialelor, care cresc foarte rapid, astfel încât dacă $\log_2 n = x$log, start base, 2, end base, n, equals, x, atunci $n = 2^x$n, equals, 2, start superscript, x, end superscript. De exemplu, deoarece $\log_2 128 = 7$log, start base, 2, end base, 128, equals, 7, avem $2^7 = 128$2, start superscript, 7, end superscript, equals, 128.

Acest lucru face ușoară calcularea timpului de execuție a unui algoritm de căutare binară pentru un $n$n care este exact o putere de 2. Dacă $n$n este 128, căutarea binară va necesita cel mult 8 ($\log_2 128 + 1$log, start base, 2, end base, 128, plus, 1) încercări.

Ce se întâmplă dacă $n$n nu este o putere de 2? În acest caz, ne putem uita la cea mai apropiată putere a lui 2 mai mică decât numărul respectiv. Pentru un vector a cărui lungime este 1000, cea mai apropiată putere a lui 2 mai mică decât 1000 este 512, ceea ce înseamnă $2^{9}$2, start superscript, 9, end superscript. Astfel, putem estima că $\log_2 1000$log, start base, 2, end base, 1000 este un număr mai mare de 9 și mai mic de 10, sau folosim un calculator pentru a vedea că este aproximativ 9,7. Adunând unu la această valoare rezultă aproximativ 10.7. În cazul unei zecimale, rotunjim prin lipsă pentru a găsi numărul real de încercări. Prin urmare, pentru un vector cu 1000 de elemente, ar fi necesară o căutare binară cu cel mult 10 încercări.

Pentru catalogul de stele Tycho-2, cu 2.539.913 stele, cea mai apropiată putere a lui 2 mai mică este $2^{21}$2, start superscript, 21, end superscript (adică 2.097.152), așa că am avea nevoie de cel mult 22 de încercări. Mult mai bine decât căutarea liniară!

Mai jos, comparăm $n$n cu $\log _{2} n$log, start base, 2, end base, n:

În următorul tutorial, vom vedea cum oamenii de știință din informatică caracterizează timpul de execuție pentru căutarea liniară și pentru căutarea binară, utilizând o notație care ține cont de cea mai importantă parte a timpului de execuție și renunță la părțile mai puțin importante.

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.