1155 - 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 si precizări

• 1 ≤ n ≤ 25000
• 1 ≤ m ≤ 200000
• elementele celor 2 vectori vor fi mai mici decât 1.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

Rezolvare

def validate_input(n, a, m, b):
    # Verificare pentru n
    if not (1 <= n <= 25000):
        print("Valoarea lui n nu respectă restricțiile.")
        return False

    # Verificare pentru elementele vectorului a
    if any(not -1000000000 <= ai <= 1000000000 for ai in a):
        print("Elementele vectorului a depășesc limita de 1.000.000.000.")
        return False

    # Verificare pentru m
    if not (1 <= m <= 200000):
        print("Valoarea lui m nu respectă restricțiile.")
        return False

    # Verificare pentru elementele vectorului b
    if any(not -1000000000 <= bi <= 1000000000 for bi in b):
        print("Elementele vectorului b depășesc limita de 1.000.000.000.")
        return False

    return True
def cautare_binara(arr, obiectiv):

    left, right = 0, len(arr) - 1

    while left <= right:

        mij = left + (right - left) // 2

        if arr[mij] == obiectiv:


            return True

        elif arr[mij] < obiectiv:

            left = mij + 1

        else:

            right = mij - 1

    return False

def verifica_elementele():

    n = int(input())

    x = list(map(int, input().split()))

    m = int(input())

    y = list(map(int, input().split()))

    rezultat = []

    x.sort()

    for elem in y:
        if cautare_binara(x, elem):

            rezultat.append(1)

        else:
            rezultat.append(0)

    return rezultat

def main():
    rezultat = verifica_elementele()
    print(*rezultat)

if __name__ == "__main__":
    main()