cautbin

Căutare binară

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

Se da un sir de numere ordonat 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
2 $x$ - pozitia pe care se afla elementul cel mai mic mai mare sau egal cu $x$ in sir

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$

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

* $1 ≤ $N$ ≤ 100000$
* $1 ≤ $M$ ≤ 100000$
* Elementele sirului se vor incadra pe 31 de biti

* $1 ≤ $N$ ≤ 100 000$
* $1 ≤ $M$ ≤ 100 000$
* Elementele sirului vor fi numere strict pozitive si se vor incadra pe 31 de biti

h2. Exemplu
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 3
  2 3
| 4
  4

  2

  3

|
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/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
 
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$.

h2. Probleme suplimentare

Probleme care se rezolva cu cautarea binara:

Probleme care se rezolva folosind cautarea binara:

* Infoarena "nrtri":http://infoarena.ro/problema/nrtri:arena

* 'Nrtri':problema/nrtri
* 'Fact':problema/fact
* 'Transport':problema/transport
* 'Triang':problema/triang
* 'Patrate':problema/patrate
* 'Frac':problema/frac
* 'Poligon':problema/poligon
* 'Bere':problema/br

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

3143