Împarte problema în două
O(log n) înseamnă timp logaritmic: fiecare pas taie în două munca rămasă. Deoarece înjumătățirea micșorează numerele foarte repede, dublarea datelor de intrare 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, iar un miliard de aproximativ 30. De aceea algoritmii logaritmici par instantanei chiar și pe volume uriașe de date.
Exemplul clasic este căutarea binară — dar ea funcționează doar pe date sortate. Înjumătățirea are nevoie de o ordine ca să știe ce jumătate să arunce.
O buclă de înjumătățire
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 iterații este logaritmul lui n: pentru n = 16 bucla rulează de 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 încă un pas. Operatorul // face împărțirea întreagă, așa că n rămâne un int.
Ieșire: program Python complet
n = 16
steps = 0
while n > 1:
n = n // 2
steps += 1
print("n este acum", n)
print("16 a devenit 1 în", steps, "pași")
Căutarea binară
Căutarea binară găsește o valoare într-o listă sortată verificând mereu elementul din mijloc. Dacă elementul din mijloc este prea mic, întreaga jumătate stângă este aruncată; dacă este prea mare, jumătatea dreaptă. Fiecare verificare înjumătățește intervalul de căutare.
Două marcaje, lo și hi, păstrează intervalul curent. Bucla se termină când valoarea este găsită sau când intervalul devine gol.
Python oferă și o variantă gata făcută: bisect.bisect_left() din biblioteca standard returnează indicele la care valoarea își are locul în lista sortată. Când valoarea lipsește, acest indice este poziția în care ar fi inserată.
Căutarea binară pas cu pas
Într-o listă 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 indicele 6. O căutare liniară ar fi avut nevoie aici de 7 pași — și de până la 16.
Ieșire: program Python complet
nums = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31]
target = 13
steps = 0
lo, hi = 0, len(nums) - 1
while lo <= hi:
steps += 1
mid = (lo + hi) // 2
if nums[mid] == target:
print("am găsit", target, "la indicele", mid, "după", steps, "verificări")
break
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
Căutarea binară cu modulul bisect
bisect.bisect_left() găsește 9 la indicele 4, iar compararea lui nums[i] cu valoarea confirmă găsirea. Valoarea lipsă 10 dă indicele 5 — locul în care 10 ar încăpea astfel încât lista să rămână sortată — iar comparația afișează False.
Ieșire: program Python complet
import bisect
nums = [1, 3, 5, 7, 9, 11, 13, 15]
i = bisect.bisect_left(nums, 9)
print("indice:", i, "găsit:", i < len(nums) and nums[i] == 9)
i = bisect.bisect_left(nums, 10)
print("indice:", i, "găsit:", i < len(nums) and nums[i] == 10)
O(n log n): sortarea
O(n log n) se află între timpul liniar și cel pătratic și este complexitatea algoritmilor de sortare buni: datele sunt înjumătățite iar și iar (log n niveluri), iar fiecare nivel face o cantitate liniară de muncă (n).
În Python rareori scrii singur o sortare — nums.sort() ordonează o listă pe loc, iar sorted(nums) returnează o listă nouă sortată; ambele sunt O(n log n). Să sortezi o dată și apoi să faci de multe ori căutare binară este un tipar des folosit și rapid.
Sortează o listă
nums.sort() ordonează cele 8 numere în aproximativ 8 · log 8 = 24 de pași — mult mai puțini decât cei 64 pe care i-ar folosi o sortare pătratică, iar diferența crește rapid pe măsură ce lista se mărește.
Ieșire: program Python complet
nums = [31, 5, 17, 1, 23, 9, 27, 13]
nums.sort()
print(nums)