1154 - Cautare Div Imp

Cerinta

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 iesire

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.

Restrictii si precizari

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

Iesire

0 1 1 1 0 0 0 1

Rezolvare

def cautare_divide_et_impera(x, y):

    rezultat = []

    for elem in y:

        rezultat.append(cauta_element(x, elem))

    return rezultat

def cauta_element(x, elem):

    stanga, dreapta = 0, len(x) - 1

    while stanga <= dreapta:

        mijloc = (stanga + dreapta) // 2

        if x[mijloc] == elem:

            return 1

        elif x[mijloc] < elem:

            stanga = mijloc + 1

        else:

            dreapta = mijloc - 1

    return 0

def main():

    n = int(input("Introduceți lungimea vectorului x: "))

    x = list(map(int, input("Introduceți elementele vectorului x separate prin spațiu: ").split()))

    m = int(input("Introduceți lungimea vectorului y: "))

    y = list(map(int, input("Introduceți elementele vectorului y separate prin spațiu: ").split()))

    rezultat = cautare_divide_et_impera(sorted(x), y)

    print(*rezultat)

if __name__ == "__main__":

    main()