0508 - Cautare Binara

Cerință

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 celem m elemente ale lui y.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restricțiilor impuse." 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. În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."

Restricții de precizări

• 1 ⩽ n ⩽ 25000
• 1 ⩽ m ⩽ 25000
• elementele celor 2 vectori vor fi mai mici decât 10000

Exemplul 1

Intrare

5

2 4 6 8 10

3

4 7 9

Ieșire

Datele introduse corespund restricțiilor impuse.

1 0 0

Exemplul 2

Intrare

3

1 5 7

4

3 8 1 0

Ieșire

Datele introduse corespund restricțiilor impuse.

0 0 0 0

Rezolvare ver. 1

<syntaxhighlight lang="python" line="1" start="1"> def validare(n, x, m, y):

   return str(n).isdigit() and 1 <= int(n) <= 25000 and str(m).isdigit() and 1 <= int(m) <= 2000000
   # Verifică dacă n și m sunt cifre și se află în intervalul specificat

def element_in_vector(x, y):

   result = []  # Lista în care se vor stoca rezultatele verificării
   j = 0  # Variabilă utilizată pentru a parcurge vectorul x
   for i in range(len(y)):  # Se parcurge vectorul y
       while j < len(x) and x[j] < y[i]:  # Se parcurge vectorul x până la valoarea din y[i]
           j += 1
       if j < len(x) and x[j] == y[i]:  # Dacă s-a găsit o valoare din y în x, se adaugă 1 în result
           result.append(1)
       else:  # Altfel, se adaugă 0 în result
           result.append(0)
   return result  # Se returnează lista cu rezultatele verificării

if __name__ == "__main__":

   # Citirea vectorului x
   n = int(input("Introduceți numărul de elemente în vectorul x: "))
   x = []
   for i in range(n):
       x.append(int(input(f"Introduceți elementul {i + 1} din x: ")))

   # Citirea vectorului y
   m = int(input("Introduceți numărul de elemente în vectorul y: "))
   y = []
   for i in range(m):
       y.append(int(input(f"Introduceți elementul {i + 1} din y: ")))

   if validare(n, x, m, y):
       print("Datele introduse corespund restricțiilor impuse.")
       # Verificarea elementelor din y în x
       result = element_in_vector(x, y)
       # Afișarea rezultatului
       print("Rezultatul verificării:")
       print(*result, sep=" ")
   else:
       print("Datele introduse nu corespund restricțiilor impuse.")

</syntaxhighlight>