# PBinfo #1154 – CautareDivImp – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

Cerința
Se dă un vector x cu n elemente numere naturale, și un vector y cu m elemente, de asemenea numere naturale. Folosind metoda Divide et Impera,  verificați pentru fiecare element al vectorului y dacă apare în x.

Date de intrare
Programul citește de la tastatură numărul n, iar apoi cele n elemente ale vectorului x. Apoi și citește m și cele m elemente ale lui y.

Date de ieșire
Programul va afișa pe ecran m valori 0 sau 1, separate prin exact un spațiu. A j-a valoare afișată este 1, dacă al j-lea element al șirului y apare în x, respectiv  0 în caz contrar. 

Restricții și precizări

1 ≤ n,m ≤ 1000
elementele celor doi vectori vor fi mai mici decât 1.000.000.000

Exemplu:
Intrare

7
9 6 5 14 2 1 10 
8
8 14 9 14 16 15 4 2 
Ieșire

0 1 1 1 0 0 0 1

## Cod sursă C++

```cpp
# include <iostream>
using namespace std;
int n, x[1005], m, y[1005];
void quick(int st, int dr, int v[])
{
    if(st < dr)
    {
        int i = st, j = dr, d = 0;
        while(i < j)
        {
            if(v[i] > v[j])
            {
                int aux = v[i];
                v[i] = v[j];
                v[j] = aux;
                d = 1-d;
            }
            if(d == 0)
                j--;
            else
                i++;
        }
        int k = i;
        quick(st, k-1, v);
        quick(k+1, dr, v);
    }
}
int caut(int st, int dr, int v[], int x)
{
    if(st > dr)
            return 0;
    else
    {
        int m = (st + dr)/2;
        if(v[m] == x)
            return m;
        if(v[m] > x)
            return caut(1, m-1, v, x);
        if(v[m] < x)
            return caut(m+1, dr, v, x);
        return 0;
    }
}
void citire(int &n, int v[])
{
    cin>>n;
    for(int i = 1; i <= n ; i++)
        cin>>v[i];
}
int main()
{
    citire(n, x);
    citire(m, y);
    quick(1, n, x);
    for(int i=1; i<=m; i++)
           if((caut(1, n, x, y[i])))
              cout<<1<<" ";
            else
                cout<<0<<" ";
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1154)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1154/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1154/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)