Recherche dichotomique

1. 1

   Indice

   Utiliser une boucle while. Initialiser les bornes de recherche (gauche et droite) puis les ajuster selon la comparaison avec l'élément médian.
   Écrire une fonction impérative rech_dich_imp(t: list[int], elem: int) -> int | None qui renvoie l'indice de elem dans la liste triée t, ou None si l'élément est absent. Par exemple rech_dich_imp([1, 3, 5, 7], 5) renvoie 2.
2. 2

   Indice

   Rechercher jusqu'à trouver l'élément sans pour autant que gauche soit confondu avec droite.
   On s'intéresse maintenant à des séquences dans lesquelles les éléments peuvent être répértés. Par exemple [1, 2, 2, 2, 3, 3, 5]. Écrire une fonction le_plus_a_gauche(t, elem) qui renvoie l'indice de la première occurrence de elem dans la liste triée t, ou None si l'élément est absent. Par exemple le_plus_a_gauche([1, 3, 3, 5], 3) renvoie 1.
3. 3

   Indice

   Définir le cas de base (gauche > droite) puis appeler récursivement la fonction sur le sous-tableau pertinent.
   Écrire une fonction r_dicho(t, g, d, elem) qui renvoie l'indice de elem dans le sous-table t[g:d+1], ou None si l'élément est absent. Par exemple r_dicho([1, 3, 5, 7], 0, 3, 5) renvoie 2.