Minimul unui tablou sortat și rotit
În lecția trecută ai căutat o valoare într-o listă rotită. Acum o întrebare înrudită: unde e cel mai mic element, adică punctul în care lista a fost rotită? min() îl găsește în O(n); cu o comparație ingenioasă între mijloc și capătul din dreapta îl găsești în O(log n).
Problema
Primești o listă de numere distincte, sortată și rotită, ca [3, 4, 5, 1, 2]. Returnează valoarea minimă. Dacă lista nu e rotită ([11, 13, 15, 17]), minimul e primul element.
Scrie funcția minim_rotit(lista) care returnează cel mai mic element dintr-o listă nevidă de numere distincte, sortată și rotită, în O(log n): compară mijlocul cu capătul din dreapta. Nu folosi min(), sort() sau sorted().
- Pornește cu st, dr = 0, len(lista) - 1 și bucla while st < dr.
- Dacă lista[mij] > lista[dr], mergi la dreapta (st = mij + 1), altfel dr = mij.
- Returnează lista[st]. Trebuie să apară: 1, 0, 11, 1, 5.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan