Împarte problema în două
O(log n) înseamnă timp logaritmic: fiecare pas reduce la jumătate munca rămasă. Fiindcă înjumătățirea micșorează numerele atât de repede, dublarea intrării adaugă doar un pas în plus.
16 elemente au nevoie de 4 înjumătățiri, 32 de elemente de 5, un milion de elemente de aproximativ 20, un miliard de aproximativ 30. De aceea algoritmii logaritmici par instantanei chiar și pe date uriașe.
Exemplul clasic este căutarea binară — dar ea funcționează doar pe date sortate. Înjumătățirea are nevoie de o ordine pentru a ști care jumătate se aruncă.
O buclă care înjumătățește
Cel mai simplu mod de a vedea O(log n) este o buclă care împarte n la 2 până ajunge la 1. Numărul de runde este logaritmul lui n: pentru n = 16 bucla rulează 4 ori, deoarece 2 · 2 · 2 · 2 = 16.
Înjumătățire până rămâne unu
16 devine 8, 4, 2, 1 — patru pași. Dublarea lui n la 32 ar adăuga doar un pas în plus.
Ieșire: script PHP
<?php
$n = 16;
$steps = 0;
while ($n > 1) {
$n = intdiv($n, 2);
$steps++;
echo "n este acum $n\n";
}
echo "16 a devenit 1 în $steps pași\n";
Căutare binară
Căutarea binară găsește o valoare într-un tablou sortat verificând mereu elementul din mijloc. Dacă mijlocul este prea mic, toată jumătatea din stânga este aruncată; dacă este prea mare, jumătatea din dreapta. Fiecare verificare înjumătățește intervalul de căutare.
Doi marcatori, $lo și $hi, țin intervalul curent. Bucla se termină când valoarea este găsită sau intervalul este gol.
PHP nu are o căutare binară gata făcută în biblioteca standard. Funcția integrată array_search() găsește o valoare parcurgând de la început — asta este liniar, O(n). Pe date sortate, o căutare binară scrisă de mână este unealta mai rapidă și îți poate spune și unde s-ar potrivi o valoare lipsă.
Căutarea binară pas cu pas
Într-un tablou sortat de 16 numere, căutarea valorii 13 are nevoie de doar 4 verificări: intervalul se micșorează 16 → 8 → 4 → 2 și ajunge la indexul 6. O căutare liniară ar fi avut nevoie aici de 7 pași — și de până la 16.
Ieșire: script PHP
<?php
$nums = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31];
$target = 13;
$steps = 0;
$lo = 0;
$hi = count($nums) - 1;
while ($lo <= $hi) {
$steps++;
$mid = intdiv($lo + $hi, 2);
if ($nums[$mid] === $target) {
echo "$target găsit la indexul $mid după $steps verificări\n";
break;
}
if ($nums[$mid] < $target) {
$lo = $mid + 1;
} else {
$hi = $mid - 1;
}
}
Căutare binară vs. array_search()
binarySearch() găsește 9 la indexul 4. Valoarea lipsă 10 dă găsit: false și indexul 5 — locul în care 10 s-ar potrivi pentru ca tabloul să rămână sortat. array_search() răspunde și ea, dar parcurge tabloul liniar, iar pentru valoarea lipsă 10 returnează doar false — fără poziție.
Ieșire: script PHP
<?php
function binarySearch(array $nums, int $target): array {
$lo = 0;
$hi = count($nums);
while ($lo < $hi) {
$mid = intdiv($lo + $hi, 2);
if ($nums[$mid] < $target) {
$lo = $mid + 1;
} else {
$hi = $mid;
}
}
$found = $lo < count($nums) && $nums[$lo] === $target;
return [$lo, $found];
}
$nums = [1, 3, 5, 7, 9, 11, 13, 15];
[$i, $found] = binarySearch($nums, 9);
echo "binarySearch 9 -> indice: $i găsit: ", var_export($found, true), "\n";
[$i, $found] = binarySearch($nums, 10);
echo "binarySearch 10 -> indice: $i găsit: ", var_export($found, true), "\n";
// array_search parcurge de la început: liniar, O(n).
echo "array_search 9 -> ", var_export(array_search(9, $nums, true), true), "\n";
echo "array_search 10 -> ", var_export(array_search(10, $nums, true), true), "\n";
O(n log n): sortarea
O(n log n) se află între liniar și pătratic și este complexitatea algoritmilor buni de sortare: datele sunt înjumătățite iar și iar (log n niveluri), iar fiecare nivel face o cantitate liniară de muncă (n).
În PHP rar scrii singur o sortare — sort() este O(n log n). Ea primește tabloul prin referință și îl sortează pe loc: tabloul însuși este modificat, nu trebuie atribuit nimic înapoi. Sortarea o singură dată, apoi multe căutări binare, este un tipar frecvent și rapid.
Sortarea unui tablou
sort() ordonează cele 8 numere pe loc, în aproximativ 8 · log 8 = 24 pași — mult mai puțini decât cei 64 pe care i-ar folosi o sortare pătratică, iar diferența crește repede odată cu tabloul.
Ieșire: script PHP
<?php
$nums = [31, 5, 17, 1, 23, 9, 27, 13];
sort($nums);
echo implode(", ", $nums), "\n";