| Fişierul intrare/ieşire: | cautbin.in, cautbin.out | Sursă | ad-hoc |
| Autor | Arhiva Educationala | Adăugată de |  Pripoae Teodor Anton •toni2007 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 5120 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Cautare binara
Se da un sir de numere ordonat crescator cu N elemente, si se cere sa se raspunda la M intrebari de tipul:
0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir
1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x
2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x
Date de intrare
Pe prima linie a fisierului de intrare cautbin.in se afla numarul N reprezentand numarul de elemente ale sirului. Pe urmatoarea linie se gasesc N numere reprezentand elementele sirului. Linia a treia contine numarul M reprezentand numarul de intrebari. Apoi urmeaza M linii, fiecare cu unul dintre cele 3 tipuri de intrebari.
Date de iesire
In fisierul de iesire cautbin.out se vor afisa M linii reprezentand raspunsul la cele M intrebari.
Restrictii
- 1 ≤ N ≤ 100 000
- 1 ≤ M ≤ 100 000
- Elementele sirului vor fi numere strict pozitive si se vor incadra pe 31 de biti
Exemplu
| cautbin.in | cautbin.out |
|---|---|
| 5 1 3 3 3 5 3 0 3 1 3 2 3 | 4 4 2 |
Indicatii de rezolvare
O rezolvare avand complexitatea O(N*M) obtine 40 de puncte si se poate gasi aici.
0 rezolvare folosind cautarea binara, in varianta clasica, are complexitatea 0(Mlog2N) si obtine 100 de puncte. Sursa se gaseste aici. De asemenea, o solutie cu aceeasi complexitate teoretica dar mai rapida in practica foloseste cautarea binara pe biti, despre care puteti afla mai multe in articolul Multe "smenuri" de programare in C/C++... si nu numai!. O sursa care se bazeaza pe ideea prezentata in articol se gaseste aici.
O sursa folosind cautarea binara din STL (lower_bound si upper_bound se gaseste aici.
Un alt articol foarte bun despre cautarea binara si aplicatii ale acesteia puteti gasi pe topcoder.
Recomandari de implementare
Aveti grija atunci cand calculati mijlocul intervalului de capete [st, dr]. In cazul folosirii instructiunii mid=(st+dr)/2 pot aparea erori nedorite. st+dr poate depasi tipul de data al variabilelor st si dr. De asemenea pot aparea erori in cazul in care capetele intervalului pot lua si valori negative. De aceea se recomanda scrierea instructiunii mid = lo + (hi-lo)/2 in loc de mid = (st+dr)/2.
Probleme suplimentare
Probleme care se rezolva folosind cautarea binara:
