Revizia anterioară Revizia următoare
| 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 - pozitia cea mai mare pe care se afla elementul cu valoarea x sau -1 daca nu se gaseste in sir
1 x - pozitia pe care se afla elementul cel mai mare mai mic sau egal cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x
2 x - pozitia pe care se afla elementul cel mai mic mai mare sau egal 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 alea 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 ≤ 100000
- 1 ≤ M ≤ 100000
- Elementele sirului vor fi numere strict pozitive si se vor incadra pe 31 de biti
Exemplu
| cautbin.in | cautbin.out |
|---|---|
| 5 1 3 5 8 15 3 0 3 1 2 2 7 | 2 1 4 |
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':?.
Un alt articol foarte bun despre cautarea binara si aplicatii ale acesteia puteti gasi pe pe topcoder.
Probleme suplimentare
Probleme care se rezolva folosind cautarea binara:
