Editing 1155 - Cautare Binara

Cerinta

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 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 ≤ 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 

Iesire

0 1 1 1 0 0 0 1

Rezolvare:

def cautare_binara(arr, obiectiv):

    left, right = 0, len(arr) - 1 #initializam 2 variabile , left va fi indicele de start iar

    #right indicele de final

    while left <= right:

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

        if arr[mij] == obiectiv: #Verificam daca valoarea din mijloc este egala cu obiectivul,

            #Daca da, inseamna ca am gasit elementul cautat si returnam True

            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()  # Sortăm vectorul x pentru a folosi căutarea binară

    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()