Găsirea unui element vârf
Ești pe un traseu montan cu ceață și vezi doar la un pas în față. Cum ajungi sigur pe un vârf? Simplu: mergi mereu în sus. Ideea asta, combinată cu căutarea binară, găsește un vârf într-o listă nesortată în O(log n). E dovada că căutarea binară nu are nevoie mereu de o listă sortată.
Problema
Un vârf este un element strict mai mare decât vecinii lui. Elementele din afara listei se consideră „minus infinit”, deci primul și ultimul element pot fi vârfuri. Doi vecini nu sunt niciodată egali. Returnează indexul unui vârf oarecare.
Scrie funcția varf(lista) care returnează indexul unui vârf (element strict mai mare decât vecinii; în afara listei e minus infinit) folosind căutarea binară: compară lista[mij] cu lista[mij + 1] și urcă panta. Nu folosi max() sau index().
- Pornește cu st, dr = 0, len(lista) - 1 și while st < dr.
- Dacă lista[mij] < lista[mij + 1], st = mij + 1, altfel dr = mij.
- Trebuie să apară: 2, 5, 0, 0, 4.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan