Module: Recherche linéaire et binaire d'éléments dans un tableau


Problem

7/7

Implémentation de la recherche binaire

Theory Click to read/hide

Comparaison des algorithmes de recherche linéaire et binaire par le nombre de comparaisons
 
Exemples
# Recherche de ligne Recherche binaire
2 2 2
16 16 5
1024 1024 11
1048576 1048576 21

L'avantage du tri binaire est qu'il est plus rapide.
Inconvénients : un tableau pré-trié est nécessaire.

 

Problem

Mettre en œuvre un algorithme de recherche binaire.

Données d'entrée
La première ligne de l'entrée contient des nombres naturels N et K (0<N,K<=100000). La deuxième ligne définit Néléments du premier tableau, triés par ordre croissant, et la troisième ligne définit Kéléments du second déployer. Les éléments des deux tableaux sont des nombres entiers, dont chacun ne dépasse pas 109.

Mentions légales
Il est nécessaire que chacun des nombres K sorte dans une ligne séparée "OUI" si ce nombre apparaît dans le premier tableau, et "NON< /code>" sinon.
 
Exemples
# Entrée Sortie
1 10 5
1 2 3 4 5 6 7 8 9 10
-2 0 4 9 12 		NON
NON
OUI
OUI
NON

 

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below

     

Program check result

To check the solution of the problem, you need to register or log in!