Recherche binaire
Imaginez que nous ayons inscrit la hauteur de tous les bâtiments du monde dans un tableau ordonné par ordre croissant. Le premier élément est donc le bâtiment le plus bas au monde, et le dernier représente le plus haut. Nous jouons à un jeu où, pour un nombre demandé (la hauteur d’un bâtiment), vous devez répondre par la position (l’indice) de ce bâtiment dans la liste. S’il n’existe pas de bâtiment avec la hauteur demandée, vous répondez -1.
Une approche naïve consisterait à employer une boucle
for pour parcourir chaque élément du tableau et vérifier s’il correspond à la hauteur recherchée. Dans le pire des cas, cela effectue n opérations pour chaque requête (si le nombre d’éléments dans le tableau est n).h = [...] # Hauteurs de tous les bâtiments ordonnées par ordre croissant
q = int(input()) # La hauteur demandée
for i, height in enumerate(h):
if height == q: # Si nous trouvons l'élément
print(i) # Afficher l'indice
break # Et s'arrêter
else: # Si nous n'avons pas trouvé de bâtiment de hauteur q (else signifie pas de break)
print(-1) # Afficher -1 pour indiquer que nous ne l'avons pas trouvéCependant, puisque la liste est déjà ordonnée en ordre croissant, nous remarquons que nous réalisons de nombreuses opérations redondantes. Au lieu de parcourir la liste du début à la fin, nous pourrions ignorer certaines parties superflues pour trouver plus rapidement l’indice recherché.
Étant donné que le tableau est trié en ordre croissant, une solution plus optimale est d’inspecter l’élément central du tableau. Si cet élément est plus petit que
q, on peut écarter toute la moitié gauche et se concentrer uniquement sur la partie droite. S’il est plus grand que q, on peut ignorer toute la partie droite. Répéter l’examen de l’élément du milieu et l’élimination de la moitié qui ne sert plus jusqu’à trouver l’élément recherché, c’est précisément le principe de l’algorithme Binary Search.h = [...] # Hauteurs de tous les bâtiments ordonnées par ordre croissant
q = int(input()) # La hauteur demandée
l, r = 0, len(h) # La réponse se trouve toujours entre [l; r). Notez que r est exclusif
while r - l > 1: # Il y a au moins un élément à examiner entre l et r
mid = (l + r) // 2 # On prend l’index du milieu
if h[mid] > q: # h[mid] > q => on élimine la moitié droite
r = mid
else: # h[mid] <= q => on élimine la moitié gauche
l = mid
# À la fin, h[l] devrait correspondre à l'élément recherché
print(l if h[l] == q else -1)Supposons que nous ayons un tableau de hauteurs
h = [20, 22, 23, 23, 34, 49, 52, 55, 58] et que nous cherchions l’indice du bâtiment ayant une hauteur de 49.Avec cet algorithme, nous exécuterions plusieurs itérations :
mid = (0 + 9) // 2 = 4⇒h[4] = 34≤49⇒ on élimine la partie gauche.
mid = (4 + 9) // 2 = 6⇒h[6] = 52>49⇒ on élimine la partie droite.
mid = (4 + 6) // 2 = 5⇒h[5] = 49≤49⇒ on élimine la partie gauche.
l = 5,r = 6⇒r - l == 1⇒ la boucle s’arrête et on affiche 5, carh[5] = 49.
Même si l’exemple est modeste, imaginez que nous ayons 10 milliards de bâtiments. En vérifiant un par un, on effectuerait 10 milliards d’itérations dans le pire des cas. Alors qu’en divisant par deux à chaque fois (et en ignorant la moitié non pertinente), on réalise un énorme gain de performance. Voyons combien d’itérations seraient nécessaires pour arriver à une réponse lorsque nous coupons 10 milliards d’éléments en deux à chaque étape :
Indice : seulement 32 itérations au lieu de 10 milliards
- 10,000,000,000 / 2 = 5,000,000,000
- 5,000,000,000 / 2 = 2,500,000,000
- 1250000000 / 2 = 625000000
- 625000000 / 2 = 312500000
- 312500000 / 2 = 156250000
- 156250000 / 2 = 78125000
- 78125000 / 2 = 39062500
- 39062500 / 2 = 19531250
- 19531250 / 2 = 9765625
- 9765625 / 2 = 4882812
- 4882812 / 2 = 2441406
- 2441406 / 2 = 1220703
- 1220703 / 2 = 610351
- 610351 / 2 = 305175
- 305175 / 2 = 152587
- 152587 / 2 = 76293
- 76293 / 2 = 38146
- 38146 / 2 = 19073
- 19073 / 2 = 9536
- 9536 / 2 = 4768
- 4768 / 2 = 2384
- 2384 / 2 = 1192
- 1192 / 2 = 596
- 596 / 2 = 298
- 298 / 2 = 149
- 149 / 2 = 74
- 74 / 2 = 37
- 37 / 2 = 18
- 18 / 2 = 9
- 9 / 2 = 4
- 4 / 2 = 2
- 2 / 2 = 1
Maintenant, imaginons un algorithme parcourant linéairement 10 milliards d’éléments, sachant que chaque vérification prendrait 1 seconde. Cela mettrait 317 ans pour arriver à un résultat ! Alors qu’un algorithme de recherche binaire ne prendrait que 32 secondes !
C’est la différence entre effectuer des opérations en et en .
Défi
Étant donné
n GPAs allant de 1 à 4 (1 étant la plus basse note et 4 la note parfaite), et plusieurs seuils, vous devez indiquer combien de personnes passeraient au niveau suivant si l’on considère qu’une personne passe dès qu’elle atteint ou dépasse le seuil.Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ ) qui représente le nombre d’étudiants.La ligne suivante contient
n nombres à virgule flottante représentant les GPAs des étudiants en ordre croissant (1 ≤ ≤ 4).La troisième ligne contient un entier
q (1 ≤ q ≤ ) qui représente le nombre de seuils à considérer.La dernière ligne de l’entrée contient
q nombres à virgule flottante représentant les seuils minimum pour passer au niveau suivant (1 ≤ ≤ 4).Sortie
Le programme doit afficher
q lignes. La ligne i doit représenter le nombre d’étudiants qui passeraient au niveau suivant étant donné le seuil .Exemples
Entrée | Sortie |
10
1.1 1.2 1.4 1.7 2 3 3.3 3.5 3.8 3.8
5
3.7
3.8
1
1.5
2 | 2
2
10
7
6 |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB