Bases de la programmation (trace de pseudo-code)

÷ est la division ; quand le résultat est affecté à une variable entière (y compris un argument de fonction), la partie fractionnaire est supprimée. Le programme suivant place dans lo l'indice de la première valeur supérieure ou égale à x dans le tableau d'entiers data, trié par ordre croissant (les indices commencent à 1). x n'est pas supérieur au dernier élément de data. Que faut-il écrire à la place de 【a】 dans le programme ?

integer: lo ← 1, hi ← length(data), mid
while (lo < hi)
  mid ← (lo + hi) ÷ 2
  if (data[mid] < x)
    lo ← 【a】
  else
    hi ← mid
  endif
endwhile

Amid
Bmid − 1
Cmid + 1

Afficher la réponse et l'explication

Réponse : C. mid + 1

Si data[mid] < x, data[mid] et tous les éléments qui le précèdent sont inférieurs à x : la réponse se trouve en mid + 1 ou après. Sinon, data[mid] ≧ x et la réponse se trouve en mid ou avant, d'où hi ← mid. Avec lo ← mid + 1, la plage se réduit à chaque fois, et la réponse est la position où lo = hi. Avec lo ← mid, quand lo et hi sont voisins, mid = lo, et si data[mid] < x la plage ne se réduit plus et la boucle ne se termine jamais.

S'entraîner sur ce thème Retour au thème

Autres questions sur Bases de la programmation (trace de pseudo-code)