Recherche binaire récursive
Il est parfois très pratique d’implémenter la recherche binaire de manière récursive. Vous devez écrire une fonction de recherche binaire qui renvoie l’indice du premier élément
target trouvé dans le tableau, ou -1 s’il n’apparaît pas.Entrée
La première ligne d’entrée contient deux entiers
n (1 ≤ n ≤ ), le nombre d’éléments, et q (1 ≤ q ≤ ), le nombre de requêtes.La ligne suivante contient
n entiers séparés par des espaces ( ≤ ≤ ) présentés dans l’ordre croissant.La dernière ligne contient
q entiers séparés par des espaces ( ≤ ≤ ), qui représentent les valeurs cibles.Sortie
Le programme doit afficher
q entiers correspondant au résultat pour chaque valeur cible (l’indexation commence à 0).Exemples
Input | Entrée |
9 3
20 22 23 23 34 49 52 55 58
49 22 24 | 5 1 -1 |
Constraints
Time limit: 8 seconds
Memory limit: 512 MB
Output limit: 1 MB