Căutarea binară
Cum găsești un cuvânt într-un dicționar de hârtie? Nu citești pagină cu pagină: deschizi la mijloc, vezi dacă ești prea departe sau prea aproape și arunci jumătate din carte. Asta e căutarea binară: pe o listă sortată, găsește un element în O(log n) pași. Pentru un milion de elemente: cel mult 20 de pași.
Ideea
Ții două capete, st și dr, între care se poate afla elementul. La fiecare pas te uiți la mijloc:
lista = [3, 8, 15, 23, 42, 56, 71, 89]
x = 56
st, dr = 0, len(lista) - 1
while st <= dr:
mij = (st + dr) // 2
print(f'st={st} dr={dr} mij={mij} -> {lista[mij]}') Scrie funcția cautare_binara(lista, x) care caută x într-o listă sortată crescător și returnează tuplul (index, pasi), sau (-1, pasi) dacă x nu există. pasi este numărul de iterații ale buclei while. Nu folosi index() sau operatorul in.
- Pornește cu st, dr = 0, len(lista) - 1 și pasi = 0.
- În bucla while st <= dr, crește pasi, calculează mijlocul și mută capătul potrivit.
- Lista din teste are numerele pare 0, 2, ..., 98. Trebuie să apară: (21, 6), (0, 5), (-1, 6), (-1, 0).
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan