Căutarea binară
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șipasi = 0. - În bucla
while st <= dr, creștepasi, 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).
mij = (st + dr) // 2; capetele se mută la mij + 1 sau mij - 1.def cautare_binara(lista, x):
st, dr = 0, len(lista) - 1
pasi = 0
while st <= dr:
pasi += 1
mij = (st + dr) // 2
if lista[mij] == x:
return mij, pasi
if lista[mij] < x:
st = mij + 1
else:
dr = mij - 1
return -1, pasi
lista = list(range(0, 100, 2))
print(cautare_binara(lista, 42))
print(cautare_binara(lista, 0))
print(cautare_binara(lista, 51))
print(cautare_binara([], 7))


