Recherche d'un badge dans un fichier trié : dichotomie qui boucle
Le club de robotique d'un lycée dispose d'un fichier de 12 000 numéros de badges, stockés dans un tableau Python trié par ordre croissant. Pour retrouver rapidement le badge d'un élève à l'entrée du gymnase, Léa propose la fonction suivante :
def recherche(tab, cible):
debut = 0
fin = len(tab)
while debut < fin:
milieu = (debut + fin) // 2
if tab[milieu] == cible:
return milieu
elif tab[milieu] < cible:
debut = milieu
else:
fin = milieu
return -1
Lors des tests, la recherche d'un badge absent dont le numéro est supérieur à tous ceux du fichier ne rend jamais la main. La recherche d'un numéro absent situé entre deux badges existants boucle également. Pourtant, la recherche d'un badge présent semble fonctionner. Le surveillant veut savoir si l'algorithme est réellement dichotomique et s'il peut servir pour vérifier qu'un badge n'a pas déjà été utilisé.
1. Expliquer précisément, avec un petit tableau de valeurs, pourquoi la boucle ne termine pas pour une cible absente, puis corriger la fonction en une seule ligne modifiée. Justifier que la correction préserve la terminaison.
Read the worked answer
Prenons tab = [2, 5, 9] et cible = 7. Au départ debut = 0, fin = 3, donc milieu = 1 et tab[1] = 5 < 7 : on exécute debut = milieu, soit debut = 1. Ensuite milieu = (1 + 3) // 2 = 2, tab[2] = 9 > 7 : on exécute fin = 2. Puis milieu = (1 + 2) // 2 = 1, tab[1] = 5 < 7 : on réexécute debut = 1. L'état (debut, fin) = (1, 2) se répète indéfiniment : l'intervalle ne rétrécit plus. Le défaut est que debut = milieu ne rejette pas la position milieu déjà testée. La correction est debut = milieu + 1 dans la branche tab[milieu] < cible. La branche fin = milieu est correcte car l'intervalle est semi-ouvert [debut, fin[. Chaque itération réduit alors strictement la taille fin - debut d'au moins 1, donc la boucle termine. Il faut aussi vérifier le cas tab vide : fin = 0, la boucle ne s'exécute pas et on renvoie -1.
2. Donner la complexité temporelle de la version corrigée en fonction de n, puis comparer le nombre maximal d'itérations pour n = 12 000 et n = 1 000 000 avec une recherche linéaire. Expliquer pourquoi la dichotomie exige un tableau trié.
Read the worked answer
À chaque itération, on divise la taille de l'intervalle de recherche par 2 : la complexité temporelle est O(log2 n) et la complexité spatiale est O(1). Pour n = 12 000, on a 2^13 = 8192 et 2^14 = 16384, donc au plus 14 itérations. Pour n = 1 000 000, 2^20 ≈ 1,05 × 10^6, donc au plus 20 itérations. Une recherche linéaire ferait jusqu'à 12 000 puis 1 000 000 de comparaisons dans le pire cas. La dichotomie n'est valide que si le tableau est trié : la comparaison tab[milieu] < cible permet de conclure que toute la moitié gauche est strictement inférieure à la cible. Sans tri, cette conclusion est fausse et on peut éliminer la position où se trouve la cible.
3. Le fichier contient des doublons : deux badges peuvent avoir le même numéro. La fonction renvoie-t-elle toujours le premier indice ? Expliquer et proposer une modification si l'on veut le premier.
Read the worked answer
Non. Exemple tab = [1, 2, 2, 2, 3], cible = 2 : debut = 0, fin = 5, milieu = 2, tab[2] = 2, la fonction renvoie 2, qui n'est pas le premier indice (0). Selon les valeurs, elle peut renvoyer n'importe quelle occurrence. Pour obtenir la première occurrence, on ne renvoie pas immédiatement quand on trouve : on note l'indice dans une variable resultat, puis on continue à chercher à gauche avec fin = milieu. À la fin, on renvoie resultat ou -1. Il faut conserver la condition debut < fin et ne pas utiliser debut = milieu pour la recherche à gauche. La complexité reste O(log n), mais il faut parfois un tour de plus.