\documentclass[a4paper,11pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais,bloc,completemulti]{automultiplechoice}
\usepackage[french]{babel}
\usepackage{amsmath, amssymb}

\title{Recherche dichotomique}
\date{Numérique et sciences informatiques}

\begin{document}

\noindent\textbf{Recherche dichotomique} \hfill \textit{Numérique et sciences informatiques}\\[0.4em]
Nom~: \dotfill\ Prénom~: \dotfill

\bigskip

\element{premiererecherchedichotomique}{
  \begin{question}{q01}
    Quel est le principe de la \textbf{recherche dichotomique} ?
    \begin{choices}
    \wrongchoice{Trier la liste avant chaque comparaison}
    \wrongchoice{Utiliser un dictionnaire}
    \wrongchoice{Parcourir la liste élément par élément}
    \correctchoice{Comparer la cible à l'élément du milieu, puis répéter sur la moitié appropriée}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q02}
    La recherche dichotomique exige-t-elle une
condition particulière sur la liste ?
    \begin{choices}
    \wrongchoice{La liste doit être de taille au moins 100}
    \wrongchoice{La liste doit être de longueur paire}
    \wrongchoice{La liste doit contenir uniquement des entiers}
    \correctchoice{La liste doit être triée}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q03}
    Quelle est la \textbf{complexité dans le pire cas} de
la recherche dichotomique ?
    \begin{choices}
    \wrongchoice{O(1)}
    \wrongchoice{O(n log n)}
    \correctchoice{O(log n)}
    \wrongchoice{O(n)}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q04}
    Avec deux indices \texttt{g} (gauche) et \texttt{d} (droite),
comment calcule-t-on l'\textbf{indice du milieu} en
Python ?
    \begin{choices}
    \correctchoice{\texttt{m = (g + d) // 2}}
    \wrongchoice{\texttt{m = g - d}}
    \wrongchoice{\texttt{m = g + d}}
    \wrongchoice{\texttt{m = (g + d) / 2}}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q05}
    Si la valeur à l'indice du milieu est \textbf{plus
petite} que la cible (et la liste est triée
croissant), où chercher ensuite ?
    \begin{choices}
    \correctchoice{Dans la moitié droite}
    \wrongchoice{Dans la moitié gauche}
    \wrongchoice{Dans toute la liste}
    \wrongchoice{Au milieu, à nouveau}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q06}
    Quel code implémente correctement la recherche
dichotomique itérative (renvoie l'indice ou -1) ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def dicho(liste, cible):
    g, d = 0, len(liste)
    while g < d:
        m = (g + d) // 2
        if liste[m] == cible:
            return m
        g = m
        d = m
    return -1
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def dicho(liste, cible):
    for x in liste:
        if x == cible:
            return x
    return -1
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
def dicho(liste, cible):
    g, d = 0, len(liste) - 1
    while g <= d:
        m = (g + d) // 2
        if liste[m] == cible:
            return m
        elif liste[m] < cible:
            g = m + 1
        else:
            d = m - 1
    return -1
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def dicho(liste, cible):
    return liste.index(cible)
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q07}
    Dans le code itératif \texttt{while g <= d:}, quand la
boucle se termine-t-elle si la cible est absente ?
    \begin{choices}
    \wrongchoice{Quand \texttt{g == d}}
    \wrongchoice{Au bout de 10 itérations}
    \correctchoice{Quand \texttt{g > d} (les deux indices se sont croisés)}
    \wrongchoice{Quand on rencontre une exception}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q08}
    Que renvoie la dichotomie sur une \textbf{liste vide} ?
    \begin{choices}
    \wrongchoice{\texttt{None}}
    \wrongchoice{Une exception}
    \correctchoice{\texttt{-1}}
    \wrongchoice{\texttt{0}}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q09}
    Quel est le principal \textbf{avantage} de la
dichotomique sur la linéaire ?
    \begin{choices}
    \wrongchoice{Elle est plus simple à programmer}
    \wrongchoice{Elle utilise moins de mémoire}
    \wrongchoice{Elle ne nécessite pas que la liste soit triée}
    \correctchoice{Elle est exponentiellement plus rapide sur les listes triées de grande taille}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q10}
    On cherche \texttt{cible = 17} dans
\texttt{liste = [3, 7, 11, 17, 25, 31, 42]}. Quel est
l'indice du milieu à la \textbf{première étape} ?
    \begin{choices}
    \wrongchoice{4}
    \wrongchoice{6}
    \correctchoice{3}
    \wrongchoice{0}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q11}
    Quel \textbf{invariant de boucle} garantit la
correction de la recherche dichotomique
itérative (avec les indices \texttt{g} et \texttt{d}) ?
    \begin{choices}
    \wrongchoice{La cible est toujours à l'indice du milieu}
    \wrongchoice{La liste est triée}
    \correctchoice{Si la cible est dans la liste, alors elle se trouve nécessairement dans la tranche \texttt{liste[g..d]} (notation algorithmique inclusive des deux côtés ; en Python : \texttt{liste[g:d+1]})}
    \wrongchoice{\texttt{g} et \texttt{d} sont toujours égaux}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q12}
    Si la cible apparaît \textbf{plusieurs fois} dans la
liste triée, quelle position renvoie la
dichotomie standard ?
    \begin{choices}
    \correctchoice{Une occurrence quelconque (la première rencontrée pendant la dichotomie)}
    \wrongchoice{La dernière occurrence (à droite)}
    \wrongchoice{Toutes les occurrences}
    \wrongchoice{La première occurrence (à gauche)}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q13}
    On cherche \texttt{cible = 25} dans
\texttt{liste = [3, 7, 11, 17, 25, 31, 42]}. Combien de
comparaisons effectue la dichotomie itérative
avant de trouver la cible ?
    \begin{choices}
    \wrongchoice{1}
    \wrongchoice{7}
    \correctchoice{2}
    \wrongchoice{3}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q14}
    On cherche \texttt{cible = 20} dans
\texttt{liste = [3, 7, 11, 17, 25, 31, 42]}. Que
renvoie la dichotomie ?
    \begin{choices}
    \wrongchoice{Une exception}
    \wrongchoice{L'indice 4 (position où 20 devrait être inséré)}
    \wrongchoice{La valeur 17 (la plus proche)}
    \correctchoice{-1 (élément absent)}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q15}
    Un élève écrit \texttt{while g < d:} au lieu de
\texttt{while g <= d:}. Quel est l'effet ?
    \begin{choices}
    \wrongchoice{La fonction est plus rapide}
    \wrongchoice{La fonction renvoie toujours -1}
    \correctchoice{La fonction rate la cible quand elle est en position telle que \texttt{g == d} à la fin}
    \wrongchoice{Boucle infinie}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q16}
    Une dichotomie standard sur la liste
\texttt{[3, 7, 11, 17, 25, 31, 42]} cherche \texttt{cible = 17}.
Que renvoie-t-elle ?
    \begin{choices}
    \correctchoice{L'indice \texttt{3}}
    \wrongchoice{La longueur de la liste, c'est-à-dire \texttt{7}}
    \wrongchoice{La position \texttt{0} (la première de la liste)}
    \wrongchoice{La valeur \texttt{17}}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q17}
    Sur \texttt{liste = [42]} et \texttt{cible = 42}, combien
d'itérations effectue la dichotomie standard ?
    \begin{choices}
    \correctchoice{1 (une seule itération suffit)}
    \wrongchoice{0 (la cible est trouvée sans entrer dans la boucle)}
    \wrongchoice{2}
    \wrongchoice{Boucle infinie}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q18}
    On a une liste \textbf{non triée} de 1000 éléments
sur laquelle on doit faire \textbf{une seule}
recherche. Faut-il la trier avant pour faire de
la dichotomie ?
    \begin{choices}
    \wrongchoice{Oui, parce que dichotomique = mieux}
    \wrongchoice{Oui, c'est plus rapide}
    \wrongchoice{La dichotomie fonctionne sur une liste non triée}
    \correctchoice{Non, la recherche linéaire suffit pour une recherche unique}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q19}
    Pour trouver la \textbf{plus petite valeur ≥ cible}
dans une liste triée, peut-on utiliser une
dichotomie ?
    \begin{choices}
    \wrongchoice{Oui, mais cela double la complexité}
    \wrongchoice{Non, la dichotomie ne fonctionne que pour des comparaisons d'égalité}
    \wrongchoice{Non, cela demande une recherche linéaire}
    \correctchoice{Oui, en adaptant légèrement le code de la dichotomie}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q20}
    Pourquoi la dichotomie itérative \textbf{se termine}
toujours (pas de boucle infinie) ?
    \begin{choices}
    \correctchoice{Parce qu'à chaque itération, l'intervalle \texttt{[g, d]} se rétrécit strictement}
    \wrongchoice{Parce que Python limite les boucles à 1000 itérations}
    \wrongchoice{Parce que la cible est forcément trouvée}
    \wrongchoice{Parce que la liste est triée}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q21}
    Un élève écrit \texttt{g = m} (au lieu de \texttt{g = m + 1})
après une comparaison \texttt{liste[m] < cible}. Que se
passe-t-il ?
    \begin{choices}
    \wrongchoice{La fonction est plus rapide}
    \wrongchoice{La fonction lève une exception}
    \wrongchoice{La fonction renvoie toujours -1}
    \correctchoice{Boucle infinie possible si \texttt{g + d} est pair (donc \texttt{m == g})}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q22}
    On cherche \texttt{cible = 2} dans
\texttt{liste = [1, 2, 3, 4, 5, 6, 7, 8]} (n=8). Quels
sont les indices \texttt{m} successivement testés par
la dichotomie itérative ?
    \begin{choices}
    \wrongchoice{3, 1, 2}
    \wrongchoice{4 puis 2}
    \correctchoice{3 puis 1}
    \wrongchoice{0, 1, 2 (parcours du début)}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q23}
    Quel est le \textbf{variant de boucle} (quantité qui
décroît strictement) de la dichotomie ?
    \begin{choices}
    \wrongchoice{La valeur du milieu \texttt{m}}
    \wrongchoice{La cible}
    \wrongchoice{L'indice \texttt{g}}
    \correctchoice{La taille de l'intervalle de recherche, \texttt{d - g + 1}}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q24}
    On dispose d'un fichier trié de \textbf{10 milliards}
d'enregistrements (sur disque). Quel impact
pratique a la dichotomie ?
    \begin{choices}
    \wrongchoice{Cela ne fonctionne pas hors mémoire vive}
    \wrongchoice{10 milliards d'accès disque sont nécessaires}
    \wrongchoice{Aucun, la lecture séquentielle est aussi rapide}
    \correctchoice{~ 34 accès disque suffisent (log₂(10¹⁰) ≈ 33,2)}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q25}
    Parmi les affirmations suivantes sur la
recherche dichotomique, laquelle est \textbf{fausse} ?
    \begin{choices}
    \wrongchoice{Sa complexité est O(log n)}
    \wrongchoice{Elle ne fonctionne que sur des listes triées}
    \wrongchoice{Des variantes adaptées du code permettent de localiser la première ou la dernière occurrence en cas de doublons}
    \correctchoice{Elle est toujours plus rapide que la recherche linéaire}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q26}
    Quel code implémente correctement une \textbf{version
récursive} de la recherche dichotomique
(renvoie l'indice ou \texttt{-1}) ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def dicho(liste, cible, g, d):
    if g >= d:
        return -1
    m = (g + d) // 2
    if liste[m] == cible:
        return m
    return dicho(liste, cible, g, d)
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
def dicho(liste, cible, g, d):
    if g > d:
        return -1
    m = (g + d) // 2
    if liste[m] == cible:
        return m
    elif liste[m] < cible:
        return dicho(liste, cible, m + 1, d)
    else:
        return dicho(liste, cible, g, m - 1)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def dicho(liste, cible, g, d):
    m = (g + d) // 2
    if liste[m] == cible:
        return m
    elif liste[m] < cible:
        return dicho(liste, cible, m + 1, d)
    else:
        return dicho(liste, cible, g, m - 1)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def dicho(liste, cible):
    if len(liste) == 0:
        return -1
    m = len(liste) // 2
    if liste[m] == cible:
        return m
    elif liste[m] < cible:
        return dicho(liste[m+1:], cible)
    else:
        return dicho(liste[:m], cible)
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q27}
    Une recherche dichotomique sur une liste de
taille \texttt{n} effectue au pire \texttt{k} comparaisons.
Combien de comparaisons effectue-t-elle au pire
sur une liste de taille \texttt{2n} ?
    \begin{choices}
    \wrongchoice{\texttt{2k}}
    \wrongchoice{\texttt{k}}
    \correctchoice{\texttt{k + 1}}
    \wrongchoice{\texttt{k²}}
    \end{choices}
  \end{question}
}

\element{premiererecherchedichotomique}{
  \begin{question}{q28}
    On dispose d'une liste triée de booléens (par
exemple \texttt{[False, False, False, True, True, True]})
et on cherche l'indice de la \textbf{première}
occurrence de \texttt{True}. Quel principe permet de
résoudre ce problème en \texttt{O(log n)} ?
    \begin{choices}
    \wrongchoice{Compter les \texttt{True} puis renvoyer leur position}
    \wrongchoice{Une recherche linéaire suffit, on ne peut pas faire mieux}
    \wrongchoice{Trier la liste de booléens à nouveau}
    \correctchoice{Une dichotomie adaptée : on regarde le
milieu, si c'est \texttt{True} la frontière est à
gauche ou ici, sinon elle est strictement à
droite ; on rétrécit l'intervalle jusqu'à
isoler la frontière
}
    \end{choices}
  \end{question}
}


\onecopy{1}{
  \shufflegroup{premiererecherchedichotomique}
  \insertgroup{premiererecherchedichotomique}
}

\end{document}
