Cautbin

Căutare binară

h2. 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.

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.

h2. Date de iesire

h2. Indicatii de rezolvare

O rezolvare avand complexitatea $O(N*M)$ obtine $40$ de puncte si se poate gasi 'aici':/job_detail/181397?action=view-source.
0 rezolvare folosind "cautarea binara":http://en.wikipedia.org/wiki/Binary_search, in varianta clasica, are complexitatea $0(Mlog{~2~}N)$ si obtine $100$ de puncte. Sursa se gaseste 'aici':job_detail/194421?action=view-source. 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!':multe-smenuri-de-programare-in-cc-si-nu-numai. O sursa care se bazeaza pe ideea prezentata in articol se gaseste 'aici':job_detail/194420?action=view-source.

O rezolvare avand complexitatea $O(N*M)$ obtine $40$ de puncte si se poate gasi 'aici':job_detail/181397?action=view-source.
0 rezolvare folosind "cautarea binara":http://en.wikipedia.org/wiki/Binary_search, in varianta clasica, are complexitatea $0(Mlog{~2~}N)$ si obtine $100$ de puncte. Sursa se gaseste 'aici':job_detail/394150?action=view-source. 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!':multe-smenuri-de-programare-in-cc-si-nu-numai. O sursa care se bazeaza pe ideea prezentata in articol se gaseste 'aici':job_detail/194420?action=view-source.
O sursa folosind cautarea binara din STL (lower_bound si upper_bound se gaseste 'aici':job_detail/394141?action=view-source.

Un alt articol foarte bun despre cautarea binara si aplicatii ale acesteia puteti gasi pe 'topcoder':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch.
h2. Recomandari de implementare