#508
Se dă un vector x
cu n
elemente numere naturale, ordonate crescător, și un vector y
cu m
elemente, de asemenea numere naturale. 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 ≤ 25000
1 ≤ m ≤ 200000
- elementele celor
2
vectori vor fi mai mici decât1.000.000.000
Exemplu
Intrare
7 1 2 5 6 9 10 14 8 8 14 9 14 16 15 4 2
Ieșire
0 1 1 1 0 0 0 1
#include <iostream> #include <cassert> using namespace std; int n,m,x[25005]; int main() { cin >> n; for(int i = 0; i < n ; i++) assert(cin >> x[i]); cin >> m; for( ; m ; --m) { int y, p = -1, st = 0, dr = n-1; assert(cin >> y); while(st <= dr) { int mijloc = (st + dr) / 2; if(x[mijloc] == y) { p = mijloc; break; } else if(x[mijloc] > y) dr = mijloc - 1; else st = mijloc + 1; } if(p == -1) cout << "0 "; else cout << "1 "; } cout << endl; return 0; }
#include <iostream> using namespace std; int cautare_binara(int st,int dr,int x[],int target) { if(st > dr) return 0; int mij = (st + dr) / 2; if(x[mij] == target) return 1; if(target > x[mij]) return cautare_binara(mij+1, dr, x, target); else return cautare_binara(st, mij-1, x, target); } int main() { int x[25001],n,m,aux; cin>>n; for(int i=1;i<=n;i++) cin>>x[i]; cin>>m; for(int i=1;i<=m;i++) { cin>>aux; cout<<cautare_binara(1, n, x, aux)<<" "; } }