Căutarea binară găsește un element într-o listă sortată în timp O(log n). Ideea: comparăm elementul căutat cu mijlocul listei; dacă e mai mic, continuăm doar în jumătatea stângă, dacă e mai mare, doar în cea dreaptă. Repetăm până găsim elementul sau intervalul devine vid.

python.py

def cautare_binara(lista, x):

stanga, dreapta = 0, len(lista) - 1

while stanga <= dreapta:

mijloc = (stanga + dreapta) // 2

if lista[mijloc] == x:

return mijloc

elif lista[mijloc] < x:

stanga = mijloc + 1

else:

dreapta = mijloc - 1

return -1 # nu a fost găsit

print(cautare_binara([1, 3, 5, 7, 9, 11], 7)) # 3

print(cautare_binara([1, 3, 5, 7, 9, 11], 4)) # -1

De ce e rapidă? La fiecare pas eliminăm jumătate din lista rămasă. Pentru 1000 de elemente, în loc de 1000 de pași, ajungem la rezultat în maxim ~10 pași (log₂1000 ≈ 10).

Interclasarea combină două liste deja sortate într-una singură, sortată, parcurgându-le simultan și alegând mereu cea mai mică valoare disponibilă. E baza sortării prin interclasare (modulul 2.19).

python.py

def interclaseaza(a, b):

rez = []

i = j = 0

while i < len(a) and j < len(b):

if a[i] <= b[j]:

rez.append(a[i]); i += 1

else:

rez.append(b[j]); j += 1

rez.extend(a[i:]); rez.extend(b[j:])

return rez

print(interclaseaza([1, 4, 7], [2, 3, 8])) # [1, 2, 3, 4, 7, 8]

Sfaturi & Bune Practici Didactice

:::atentie

Fiecare funcție recursivă trebuie să aibă cel puțin un caz de bază (condiție de oprire) bine definit, altfel va rezulta o eroare de tip RecursionError (stack overflow)!

Concept nou și exemplu