Recherche binaire approximative
Problem
Mettre en œuvre un algorithme de recherche binaire approximatif.
Saisie :
- la première ligne de l'entrée contient les nombres N et K (\(0< N,\ K < ; 100001\));
- la seconde ligne contient les N nombres du premier tableau, triés par ordre non décroissant ;
- la troisième ligne contient les numéros K du deuxième tableau.
Chaque nombre dans les deux tableaux ne dépasse pas \(2 \cdot 10^9\).
Sortie : Pour chacun des nombres K, imprimez le nombre du premier tableau le plus proche du nombre donné sur une ligne distincte. S'il y en a plusieurs, imprimez le plus petit.
Exemples
| # |
Entrée |
Sortie |
| 1 |
5 5
1 3 5 7 9
2 4 8 1 6
1
3
7
1
5 |