Cautbin

Căutare binară

== include(page="template/taskheader" task_id="cautbin") ==
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$

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$

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

table(example). |_. cautbin.in |_. cautbin.out |
| 5

  1 3 5 8 15

  1 3 3 3 5

  3
  0 3

  1 2
  2 7
| 2
  1

  1 3
  2 3
| 4

  4

  2

|
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/181398?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

* 'Patrate':problema/patrate
* 'Frac':problema/frac
* 'Poligon':problema/poligon

* 'Bere':problema/br

== include(page="template/taskfooter" task_id="cautbin") ==

==SmfTopic(topic_id="3143")==

3143