Căutarea într-un tablou sortat și rotit
Un ceas digital afișează orele unei ture de noapte: 22, 23, 0, 1, 2, 3. Lista e sortată, dar rotită: a fost „tăiată” într-un punct și capetele au schimbat locul. Căutarea binară obișnuită nu mai merge direct, dar o observație simplă o repară: la fiecare pas, cel puțin o jumătate este sortată.
Problema
Primești o listă de numere distincte, sortată crescător și apoi rotită cu un număr necunoscut de poziții, de exemplu [4, 5, 6, 7, 0, 1, 2] (din [0, 1, 2, 4, 5, 6, 7]). Găsește indexul lui x sau returnează -1, în O(log n).
sortata = [0, 1, 2, 4, 5, 6, 7]
for k in [0, 3, 5]:
print('rotită cu', k, ':', sortata[k:] + sortata[:k]) Scrie funcția cauta_rotit(lista, x) care returnează indexul lui x într-o listă de numere distincte, sortată și rotită, sau -1, în O(log n). La fiecare pas, află care jumătate e sortată și verifică dacă x se află în ea. Nu folosi index() sau…
- Căutare binară obișnuită cu st, dr, mij.
- Dacă lista[st] <= lista[mij], stânga e sortată: verifică lista[st] <= x < lista[mij]. Altfel, dreapta e sortată.
- Trebuie să apară: 4, -1, 0, 1, 1.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan