Borne supérieure
Étant donné un tableau de
n entiers triés, vous devez répondre à q requêtes. Chaque requête consiste à déterminer : «Quel est le premier nombre strictement plus grand que x dans la liste donnée ?».Entrée
La première ligne de l’entrée contient deux entiers
n (2 ≤ n ≤ ) et q (1 ≤ q ≤ ).La ligne suivante contient
n entiers séparés par des espaces, notés ( ≤ ≤ ), présentés dans l’ordre croissant.La dernière ligne contient
q requêtes séparées par des espaces, notées ( ≤ < ).Sortie
Le programme doit afficher
q lignes, chacune contenant la réponse à la requête correspondante.Exemples
Entrée | Sortie |
6 3
2 7 9 10 20 30
8 20 1 | 9
30
2 |
Indice
Dans l’implémentation classique de la recherche binaire (binary search), on considère l’intervalle
[l; r) où l est inclus et r est exclu. Dans certains cas, vous pourriez vouloir travailler avec (l; r] — exclure l et inclure r. Cela nécessite d’ajuster la manière dont vous gérez les bornes l, r et la position mid.Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB