EnglishCommencer

Recherche dichotomique

Chercher dans un tableau trié en coupant l'intervalle en deux : bornes gauche et droite, milieu, moitié gardée, condition d'arrêt, mises à jour des bornes et nombre maximal d'étapes.

  • 25 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 dichotomique : de quoi s'agit-il ?

    Voir la réponse

    Algorithme qui compare la valeur cherchée à l'élément du milieu d'un tableau trié, puis ne garde que la moitié où elle peut se trouver.

    Chaque comparaison divise l'intervalle par deux : un million de cases se règlent en une vingtaine d'étapes, là où une recherche séquentielle en demande jusqu'à un million.

  • Qu'affiche ce programme ?

    ```python
    def binary_search(t, v):
    g, d = 0, len(t) - 1
    while g <= d:
    m = (g + d) // 2
    if t[m] == v:
    return m
    elif t[m] < v:
    g = m + 1
    else:
    d = m - 1
    return -1

    t = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
    print(binary_search(t, 23))
    `

    • 5
    • 4
    • 6
    • -1
    Voir la réponse

    5

    Premier milieu : m = 4, t[4] vaut 16, plus petit que 23, donc g = 5. Deuxième milieu : m = 7, 56 est trop grand, donc d = 6. Troisième milieu : m = 5, t[5] vaut 23, trouvé en trois comparaisons.

  • Le milieu de l'intervalle se calcule par m = (g + d) // 2, et quand t[m] < v on continue à droite avec ….

    Voir la réponse

    Le milieu de l'intervalle se calcule par m = (g + d) // 2, et quand t[m] < v on continue à droite avec g = m + 1.

    La case m vient d'être comparée et ne convient pas : elle doit sortir de l'intervalle. Sans le + 1, la même case revient à chaque tour.

  • Précondition de tri : de quoi s'agit-il ?

    Voir la réponse

    Condition qui doit être vraie avant l'appel de la recherche : les éléments sont déjà rangés dans l'ordre croissant.

    Si elle est fausse, la fonction ne signale aucune erreur : elle répond simplement faux, par exemple « absent » pour une valeur pourtant présente.

Réviser ce deck