\documentclass[10pt,aspectratio=169]{beamer}

% --- Thème ---
\usetheme[language=french]{Celestia}

% Avec [allowframebreaks] sur les frames de questions, Beamer ajoute
% par défaut « (1) », « (2) », « (3) »... sur chaque sous-slide. On
% supprime entièrement cette annotation : un template vide pour
% « frametitle continuation ». L'enseignant identifie visuellement la
% continuation par le contenu de la slide. (Les variantes [from second]
% et [roman] interagissent mal avec un titre contenant \textemdash{}
% sous Celestia : elles déclenchent une erreur « Missing $ inserted ».)
\setbeamertemplate{frametitle continuation}{}

\subject{Numérique et sciences informatiques}
\title{Recherche dichotomique}
\subtitle{QCM}
\author{Première}
\date{\today}

\begin{document}

\begin{frame}
    \titlepage
\end{frame}

% Q1 - Réponse en D
\begin{frame}[fragile]{Question 1 \textemdash{} Principe}
    Quel est le principe de la \textbf{recherche dichotomique} ?\medskip
    \begin{itemize}
        \item[A.] Trier la liste avant chaque comparaison
        \item[B.] Utiliser un dictionnaire
        \item[C.] Parcourir la liste élément par élément
        \item[\alert<2>{D.}] \alert<2>{Comparer la cible à l'élément du milieu, puis répéter sur la moitié appropriée}
    \end{itemize}
\end{frame}

% Q2 - Réponse en D
\begin{frame}[fragile]{Question 2 \textemdash{} Précondition}
    La recherche dichotomique exige-t-elle une
condition particulière sur la liste ?\medskip
    \begin{itemize}
        \item[A.] La liste doit être de taille au moins 100
        \item[B.] La liste doit être de longueur paire
        \item[C.] La liste doit contenir uniquement des entiers
        \item[\alert<2>{D.}] \alert<2>{La liste doit être triée}
    \end{itemize}
\end{frame}

% Q3 - Réponse en C
\begin{frame}[fragile]{Question 3 \textemdash{} Complexité}
    Quelle est la \textbf{complexité dans le pire cas} de
la recherche dichotomique ?\medskip
    \begin{itemize}
        \item[A.] O(1)
        \item[B.] O(n log n)
        \item[\alert<2>{C.}] \alert<2>{O(log n)}
        \item[D.] O(n)
    \end{itemize}
\end{frame}

% Q4 - Réponse en A
\begin{frame}[fragile]{Question 4 \textemdash{} Calcul du milieu}
    Avec deux indices \texttt{g} (gauche) et \texttt{d} (droite),
comment calcule-t-on l'\textbf{indice du milieu} en
Python ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{\texttt{m = (g + d) // 2}}
        \item[B.] \texttt{m = g - d}
        \item[C.] \texttt{m = g + d}
        \item[D.] \texttt{m = (g + d) / 2}
    \end{itemize}
\end{frame}

% Q5 - Réponse en A
\begin{frame}[fragile]{Question 5 \textemdash{} Élimination de moitié}
    Si la valeur à l'indice du milieu est \textbf{plus
petite} que la cible (et la liste est triée
croissant), où chercher ensuite ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Dans la moitié droite}
        \item[B.] Dans la moitié gauche
        \item[C.] Dans toute la liste
        \item[D.] Au milieu, à nouveau
    \end{itemize}
\end{frame}

% Q6 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 6 \textemdash{} Code itératif}
    Quel code implémente correctement la recherche
dichotomique itérative (renvoie l'indice ou -1) ?\medskip
    \begin{itemize}
        \item[A.]~\\
\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}

        \item[B.]~\\
\begin{lstlisting}
def dicho(liste, cible):
    for x in liste:
        if x == cible:
            return x
    return -1
\end{lstlisting}

        \item[C.]~\\
\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}

        \item[D.]~\\
\begin{lstlisting}
def dicho(liste, cible):
    return liste.index(cible)
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q6 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 6 \textemdash{} Code itératif}
    Quel code implémente correctement la recherche
dichotomique itérative (renvoie l'indice ou -1) ?\medskip
    \begin{itemize}
        \item[A.]~\\
\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}

        \item[B.]~\\
\begin{lstlisting}
def dicho(liste, cible):
    for x in liste:
        if x == cible:
            return x
    return -1
\end{lstlisting}

        \item[\alert{C.}]~\\
\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}

        \item[D.]~\\
\begin{lstlisting}
def dicho(liste, cible):
    return liste.index(cible)
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q7 - Réponse en C
\begin{frame}[fragile]{Question 7 \textemdash{} Sortie de boucle}
    Dans le code itératif \texttt{while g <= d:}, quand la
boucle se termine-t-elle si la cible est absente ?\medskip
    \begin{itemize}
        \item[A.] Quand \texttt{g == d}
        \item[B.] Au bout de 10 itérations
        \item[\alert<2>{C.}] \alert<2>{Quand \texttt{g > d} (les deux indices se sont croisés)}
        \item[D.] Quand on rencontre une exception
    \end{itemize}
\end{frame}

% Q8 - Réponse en C
\begin{frame}[fragile]{Question 8 \textemdash{} Liste vide}
    Que renvoie la dichotomie sur une \textbf{liste vide} ?\medskip
    \begin{itemize}
        \item[A.] \texttt{None}
        \item[B.] Une exception
        \item[\alert<2>{C.}] \alert<2>{\texttt{-1}}
        \item[D.] \texttt{0}
    \end{itemize}
\end{frame}

% Q9 - Réponse en D
\begin{frame}[fragile]{Question 9 \textemdash{} Pourquoi dichotomique ?}
    Quel est le principal \textbf{avantage} de la
dichotomique sur la linéaire ?\medskip
    \begin{itemize}
        \item[A.] Elle est plus simple à programmer
        \item[B.] Elle utilise moins de mémoire
        \item[C.] Elle ne nécessite pas que la liste soit triée
        \item[\alert<2>{D.}] \alert<2>{Elle est exponentiellement plus rapide sur les listes triées de grande taille}
    \end{itemize}
\end{frame}

% Q10 - Réponse en C
\begin{frame}[fragile]{Question 10 \textemdash{} Trace simple}
    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} ?\medskip
    \begin{itemize}
        \item[A.] 4
        \item[B.] 6
        \item[\alert<2>{C.}] \alert<2>{3}
        \item[D.] 0
    \end{itemize}
\end{frame}

% Q11 - Réponse en C
\begin{frame}[fragile]{Question 11 \textemdash{} Invariant de boucle}
    Quel \textbf{invariant de boucle} garantit la
correction de la recherche dichotomique
itérative (avec les indices \texttt{g} et \texttt{d}) ?\medskip
    \begin{itemize}
        \item[A.] La cible est toujours à l'indice du milieu
        \item[B.] La liste est triée
        \item[\alert<2>{C.}] \alert<2>{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]})}
        \item[D.] \texttt{g} et \texttt{d} sont toujours égaux
    \end{itemize}
\end{frame}

% Q12 - Réponse en A
\begin{frame}[fragile]{Question 12 \textemdash{} Doublons}
    Si la cible apparaît \textbf{plusieurs fois} dans la
liste triée, quelle position renvoie la
dichotomie standard ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Une occurrence quelconque (la première rencontrée pendant la dichotomie)}
        \item[B.] La dernière occurrence (à droite)
        \item[C.] Toutes les occurrences
        \item[D.] La première occurrence (à gauche)
    \end{itemize}
\end{frame}

% Q13 - Réponse en C
\begin{frame}[fragile]{Question 13 \textemdash{} Trace détaillée}
    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 ?\medskip
    \begin{itemize}
        \item[A.] 1
        \item[B.] 7
        \item[\alert<2>{C.}] \alert<2>{2}
        \item[D.] 3
    \end{itemize}
\end{frame}

% Q14 - Réponse en D
\begin{frame}[fragile]{Question 14 \textemdash{} Élément absent}
    On cherche \texttt{cible = 20} dans
\texttt{liste = [3, 7, 11, 17, 25, 31, 42]}. Que
renvoie la dichotomie ?\medskip
    \begin{itemize}
        \item[A.] Une exception
        \item[B.] L'indice 4 (position où 20 devrait être inséré)
        \item[C.] La valeur 17 (la plus proche)
        \item[\alert<2>{D.}] \alert<2>{-1 (élément absent)}
    \end{itemize}
\end{frame}

% Q15 - Réponse en C
\begin{frame}[fragile]{Question 15 \textemdash{} Bug de bornes}
    Un élève écrit \texttt{while g < d:} au lieu de
\texttt{while g <= d:}. Quel est l'effet ?\medskip
    \begin{itemize}
        \item[A.] La fonction est plus rapide
        \item[B.] La fonction renvoie toujours -1
        \item[\alert<2>{C.}] \alert<2>{La fonction rate la cible quand elle est en position telle que \texttt{g == d} à la fin}
        \item[D.] Boucle infinie
    \end{itemize}
\end{frame}

% Q16 - Réponse en A
\begin{frame}[fragile]{Question 16 \textemdash{} Indice retourné en cas de succès}
    Une dichotomie standard sur la liste
\texttt{[3, 7, 11, 17, 25, 31, 42]} cherche \texttt{cible = 17}.
Que renvoie-t-elle ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{L'indice \texttt{3}}
        \item[B.] La longueur de la liste, c'est-à-dire \texttt{7}
        \item[C.] La position \texttt{0} (la première de la liste)
        \item[D.] La valeur \texttt{17}
    \end{itemize}
\end{frame}

% Q17 - Réponse en A
\begin{frame}[fragile]{Question 17 \textemdash{} Liste à un élément}
    Sur \texttt{liste = [42]} et \texttt{cible = 42}, combien
d'itérations effectue la dichotomie standard ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{1 (une seule itération suffit)}
        \item[B.] 0 (la cible est trouvée sans entrer dans la boucle)
        \item[C.] 2
        \item[D.] Boucle infinie
    \end{itemize}
\end{frame}

% Q18 - Réponse en D
\begin{frame}[fragile]{Question 18 \textemdash{} Tri préalable utile ?}
    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 ?\medskip
    \begin{itemize}
        \item[A.] Oui, parce que dichotomique = mieux
        \item[B.] Oui, c'est plus rapide
        \item[C.] La dichotomie fonctionne sur une liste non triée
        \item[\alert<2>{D.}] \alert<2>{Non, la recherche linéaire suffit pour une recherche unique}
    \end{itemize}
\end{frame}

% Q19 - Réponse en D
\begin{frame}[fragile]{Question 19 \textemdash{} Recherche par approximation}
    Pour trouver la \textbf{plus petite valeur ≥ cible}
dans une liste triée, peut-on utiliser une
dichotomie ?\medskip
    \begin{itemize}
        \item[A.] Oui, mais cela double la complexité
        \item[B.] Non, la dichotomie ne fonctionne que pour des comparaisons d'égalité
        \item[C.] Non, cela demande une recherche linéaire
        \item[\alert<2>{D.}] \alert<2>{Oui, en adaptant légèrement le code de la dichotomie}
    \end{itemize}
\end{frame}

% Q20 - Réponse en A
\begin{frame}[fragile]{Question 20 \textemdash{} Terminaison}
    Pourquoi la dichotomie itérative \textbf{se termine}
toujours (pas de boucle infinie) ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Parce qu'à chaque itération, l'intervalle \texttt{[g, d]} se rétrécit strictement}
        \item[B.] Parce que Python limite les boucles à 1000 itérations
        \item[C.] Parce que la cible est forcément trouvée
        \item[D.] Parce que la liste est triée
    \end{itemize}
\end{frame}

% Q21 - Réponse en D
\begin{frame}[fragile]{Question 21 \textemdash{} Boucle infinie}
    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 ?\medskip
    \begin{itemize}
        \item[A.] La fonction est plus rapide
        \item[B.] La fonction lève une exception
        \item[C.] La fonction renvoie toujours -1
        \item[\alert<2>{D.}] \alert<2>{Boucle infinie possible si \texttt{g + d} est pair (donc \texttt{m == g})}
    \end{itemize}
\end{frame}

% Q22 - Réponse en C
\begin{frame}[fragile]{Question 22 \textemdash{} Trace pas à pas}
    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 ?\medskip
    \begin{itemize}
        \item[A.] 3, 1, 2
        \item[B.] 4 puis 2
        \item[\alert<2>{C.}] \alert<2>{3 puis 1}
        \item[D.] 0, 1, 2 (parcours du début)
    \end{itemize}
\end{frame}

% Q23 - Réponse en D
\begin{frame}[fragile]{Question 23 \textemdash{} Variant de boucle}
    Quel est le \textbf{variant de boucle} (quantité qui
décroît strictement) de la dichotomie ?\medskip
    \begin{itemize}
        \item[A.] La valeur du milieu \texttt{m}
        \item[B.] La cible
        \item[C.] L'indice \texttt{g}
        \item[\alert<2>{D.}] \alert<2>{La taille de l'intervalle de recherche, \texttt{d - g + 1}}
    \end{itemize}
\end{frame}

% Q24 - Réponse en D
\begin{frame}[fragile]{Question 24 \textemdash{} Recherche en mémoire externe}
    On dispose d'un fichier trié de \textbf{10 milliards}
d'enregistrements (sur disque). Quel impact
pratique a la dichotomie ?\medskip
    \begin{itemize}
        \item[A.] Cela ne fonctionne pas hors mémoire vive
        \item[B.] 10 milliards d'accès disque sont nécessaires
        \item[C.] Aucun, la lecture séquentielle est aussi rapide
        \item[\alert<2>{D.}] \alert<2>{~ 34 accès disque suffisent (log₂(10¹⁰) ≈ 33,2)}
    \end{itemize}
\end{frame}

% Q25 - Réponse en D
\begin{frame}[fragile]{Question 25 \textemdash{} Synthèse}
    Parmi les affirmations suivantes sur la
recherche dichotomique, laquelle est \textbf{fausse} ?\medskip
    \begin{itemize}
        \item[A.] Sa complexité est O(log n)
        \item[B.] Elle ne fonctionne que sur des listes triées
        \item[C.] Des variantes adaptées du code permettent de localiser la première ou la dernière occurrence en cas de doublons
        \item[\alert<2>{D.}] \alert<2>{Elle est toujours plus rapide que la recherche linéaire}
    \end{itemize}
\end{frame}

% Q26 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 26 \textemdash{} Version récursive}
    Quel code implémente correctement une \textbf{version
récursive} de la recherche dichotomique
(renvoie l'indice ou \texttt{-1}) ?\medskip
    \begin{itemize}
        \item[A.]~\\
\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}

        \item[B.]~\\
\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}

        \item[C.]~\\
\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}

        \item[D.]~\\
\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{itemize}
\end{frame}

% Q26 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 26 \textemdash{} Version récursive}
    Quel code implémente correctement une \textbf{version
récursive} de la recherche dichotomique
(renvoie l'indice ou \texttt{-1}) ?\medskip
    \begin{itemize}
        \item[A.]~\\
\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}

        \item[\alert{B.}]~\\
\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}

        \item[C.]~\\
\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}

        \item[D.]~\\
\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{itemize}
\end{frame}

% Q27 - Réponse en C
\begin{frame}[fragile]{Question 27 \textemdash{} Doublement de la taille}
    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} ?\medskip
    \begin{itemize}
        \item[A.] \texttt{2k}
        \item[B.] \texttt{k}
        \item[\alert<2>{C.}] \alert<2>{\texttt{k + 1}}
        \item[D.] \texttt{k²}
    \end{itemize}
\end{frame}

% Q28 - Réponse en D
\begin{frame}[fragile]{Question 28 \textemdash{} Dichotomie de frontière}
    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)} ?\medskip
    \begin{itemize}
        \item[A.] Compter les \texttt{True} puis renvoyer leur position
        \item[B.] Une recherche linéaire suffit, on ne peut pas faire mieux
        \item[C.] Trier la liste de booléens à nouveau
        \item[\alert<2>{D.}] \alert<2>{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{itemize}
\end{frame}

\begin{frame}[standout]{}
    Fin de l'évaluation
\end{frame}

\end{document}
