Prima și ultima poziție a unei valori
Un magazin are comenzile sortate după dată și vrei toate comenzile din 8 martie. Căutarea binară obișnuită găsește o comandă din acea zi, dar nu neapărat prima. Cu o mică modificare, după ce găsești valoarea continui să cauți spre stânga (sau spre dreapta), tot în O(log n).
Problema
Primești o listă sortată, posibil cu valori repetate, și o valoare x. Returnează [prima, ultima]: primul și ultimul index pe care apare x, sau [-1, -1] dacă nu apare.
index: 0 1 2 3 4 5 valoare: 5 7 7 8 8 10
Scrie funcția pozitii(lista, x) care returnează [prima, ultima], primul și ultimul index pe care apare x într-o listă sortată, sau [-1, -1], folosind două căutări binare (O(log n)). Poți scrie o funcție ajutătoare limita(lista, x, prima). N…
- În funcția ajutătoare, când găsești x, reține poziția și continuă în stânga (pentru prima) sau în dreapta (pentru ultima).
- pozitii returnează lista cu cele două limite.
- Trebuie să apară: [3, 4], [-1, -1], [-1, -1], [0, 4], [2, 2].
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan