View source for 508 - Cautare Binara

== Cerinţa ==
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 ≤ 25.000'''
* '''1 ≤ m ≤ 200.000'''
* elementele celor '''2''' vectori vor fi mai mici decât '''1.000.000.000'''
== Exemplul 1 ==
;Intrare
 7
 1 2 5 6 9 10 14 
 8
 8 14 9 14 16 15 4 2 
;Iesire 
 0 1 1 1 0 0 0 1
== Exemplul 2 ==
;Intrare
 30000
 1 2 5 6 9 10 14 
 8
 8 14 9 14 16 15 4 2 
;Iesire
 Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
def verifica_elemente():
    n_val = int(input("Introduceti numarul n: "))
    x_val = list(map(int, input("Introduceti elementele vectorului x: ").split()))

    m_val = int(input("Introduceti numarul m: "))
    y_val = list(map(int, input("Introduceti elementele vectorului y: ").split()))

    if not (1 <= n_val <= 25000) or not (1 <= m_val <= 200000):
        return "Datele de intrare nu corespund restrictiilor impuse"
    if max(x_val) >= 1000000000 or max(y_val) >= 1000000000:
        return "Datele de intrare nu corespund restrictiilor impuse"

    x_set = set(x_val)

    rezultat = [1 if elem in x_set else 0 for elem in y_val]

    return " ".join(map(str, rezultat))


print(verifica_elemente())
</syntaxhighlight>