1155 - Cautare Binara

From Bitnami MediaWiki
Revision as of 14:17, 2 January 2024 by Andrada378 (talk | contribs)

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

<syntaxhighlight lang="python"> 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()

</syntaxhighlight>