Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-01-21 19:14:51.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:cautbin.in, cautbin.outSursăad-hoc
AutorArhiva EducationalaAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.25 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

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.incautbin.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:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content