EnglishCommencer

Recherche séquentielle

Chercher une valeur en regardant les cases une à une : arrêt dès qu'on trouve, indice renvoyé ou valeur d'absence, première occurrence et nombre de comparaisons.

  • 24 cartes
  • 6 thèmes
  • Gratuit
Réviser ce deck

Le programme, thème par thème

Le poids de chaque thème suit celui que lui donne l'examen.

  1. Notions
  2. Questions
  3. Ranger et relier
  4. Les chiffres
  5. Mises en situation
  6. Comprendre

Quelques cartes du deck

  • Recherche séquentielle : de quoi s'agit-il ?

    Voir la réponse

    Algorithme qui compare la valeur cherchée aux éléments dans l'ordre, case après case, sans rien exiger de l'ordre du tableau.

    Elle marche sur n'importe quel tableau, trié ou non. Son coût est proportionnel à la taille : dans le pire cas, on regarde toutes les cases.

  • Qu'affiche ce programme ?

    ```python
    def find(t, v):
    for i in range(len(t)):
    if t[i] == v:
    return i
    return -1

    print(find([5, 12, 8, 12, 3], 12), find([5, 12, 8], 7))
    `

    • 1 -1
    • 3 -1
    • 1 0
    • 2 -1
    Voir la réponse

    1 -1

    Le premier appel s'arrête à la première occurrence de 12, l'indice 1. Le second regarde les trois cases sans succès et atteint le return -1 placé après la boucle.

  • Dans le pire cas, la recherche séquentielle d'une valeur dans un tableau de n cases fait … comparaisons, que la valeur soit … ou en dernière case.

    Voir la réponse

    Dans le pire cas, la recherche séquentielle d'une valeur dans un tableau de n cases fait n comparaisons, que la valeur soit absente ou en dernière case.

    Dans les deux cas, il faut regarder toutes les cases avant de conclure. Dans le meilleur cas, la valeur est en première case : une seule comparaison.

  • Sortie anticipée : de quoi s'agit-il ?

    Voir la réponse

    Interruption d'une boucle dès que son but est atteint, sans visiter les éléments restants : return ou break.

    Une fois la valeur trouvée, regarder la suite est inutile. Sans sortie anticipée, une boucle qui écrit pos = i à chaque succès rendrait la dernière occurrence au lieu de la première.

Réviser ce deck