\nLa recherche dichotomique, ou recherche par dichotomie (en anglais : binary search), est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié. Pour cela, on compare l'élément recherché avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié pertinente du tableau. \n\nSource : [Wikipedia](https://fr.wikipedia.org/wiki/Recherche_dichotomique)\n
On parcourt la liste en comparant chaque élément à celui recherché jusqu'à ce qu'on le trouve ou que l'on ait parcouru toute la liste.\n
"},{"metadata":{},"cell_type":"markdown","source":"## 1.2. Application"},{"metadata":{},"cell_type":"markdown","source":"!!! question Travail à faire\nCompéter la fonction ci-dessous pour qu'elle renvoie :\n\n- la position (indice) de l'élément dans le tableau si l'élément recherché `element` s'y trouve ;\n- `-1` sinon.\n\nRédiger une *docstring* précise (entrées, sortie, précondition(s)).\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"def recherche_naive(tableau: list, element: int) ->int:\n \"\"\"\n Condition : le tableau 'tableau' doit être trié\n Entrée : 'tableau', un tableau trié et 'element' un élment à chercher dans le tableau\n Sortie : renvoie un entier positif ou nul en cas de succès, qui correspond à la\n position de la valeur recherchée dans la tableau, et -1 en cas d’échec.\n \"\"\"\n \n for i in range(len(tableau)):\n if tableau[i] == element:\n return i\n return -1","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"
\n\n \n**Cliquer ici pour obtenir de l'aide**\n\n\n- Préconditions : accepte-t-on une liste vide ?\n- On parcourt la liste (boucle `for`) si l'élément est présent (test `if`) la fonction renvoie la position (l'indice `i`) de l'élément, si on sort de la boucle sans l'avoir trouvé, on renvoie `-1`.\n \n
"},{"metadata":{"trusted":false},"cell_type":"code","source":"# Vous pouvez faire des tests dans cette cellule...\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Cette cellule NE DOIT PAS ETRE modifiée\n# Test final de la fonction de cette partie\n# Si la fonction est correcte alors aucun message d'erreur ne devrait apparaitre après l'exécution de cette cellule\n\ntableau = [0, 1, 2, 3, 4, 5, 6, 7, 8]\nassert recherche_naive(tableau, 7) == 7","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## 1.3. Mesure du temps d'exécution"},{"metadata":{},"cell_type":"markdown","source":"On va maintenant mesurer la durée d'une recherche d'une valeur dans un tableau.\n\n>Pour cela, on va utiliser la fonction `time()` de la bibliothèque `time` de Python, qui permet de relever un temps dès qu'on l'appelle. En pratique, on va relever le temps avant de lancer la recherche puis juste après. Le temps mis par la recherche est alors la différence de ces deux temps. Il est exprimé en secondes.\n\nPour cela, on va se placer dans le pire des cas : un tableau `tableau` contenant uniquement des zéros dans lequel on cherche la valeur 1. Il est donc nécessaire de parcourir tout le tableau `tableau` pour constater l'absence de la valeur cherchée.\n\nExécuter le code suivant plusieurs fois et noter la durée moyenne de la recherche."},{"metadata":{"trusted":false},"cell_type":"code","source":"from time import time\n\ntableau = [0]*100000 # permet de créer un tableau de 100 000 zéros\n\nt0 = time() # on stocke dans t0 le temps de départ, avant le début de la recherche\nrecherche_naive(tableau, 1)\nt1 = time() # on stocke dans t1 le temps de fin, juste après la recherche\nt1 - t0 # la différence est le temps (en SECONDES) mis par la recherche","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"raw","source":"Durée moyenne de la recherche (en s) : ...... s"},{"metadata":{},"cell_type":"markdown","source":"!!! question Exercice\nVérifier que si on double la taille du tableau de départ, le temps de la recherche est approximativement doublé (on sépare la création du tableau de la recherche, comme précédemment)\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"# Votre code ici...\nfrom time import time\n\ntableau = [0]*200000 # permet de créer un tableau de 100 000 zéros\n\nt0 = time() # on stocke dans t0 le temps de départ, avant le début de la recherche\nrecherche_naive(tableau, 1)\nt1 = time() # on stocke dans t1 le temps de fin, juste après la recherche\nt1 - t0 # la différence est le temps (en SECONDES) mis par la recherche","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"!!! question Question\nQu'en est-il si on passe d'un tableau de 100 000 à 1 million de valeurs (10 fois plus grand) ? et à 10 millions de valeurs ?\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"# Tableau à 1 millions de valeurs\n\nfrom time import time\n\ntableau = [0]*1000000 # permet de créer un tableau de 100 000 zéros\n\nt0 = time() # on stocke dans t0 le temps de départ, avant le début de la recherche\nrecherche_naive(tableau, 1)\nt1 = time() # on stocke dans t1 le temps de fin, juste après la recherche\nt1 - t0 # la différence est le temps (en SECONDES) mis par la recherche","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Tableau à 10 millions de valeurs\n\nfrom time import time\n\ntableau = [0]*10000000 # permet de créer un tableau de 100 000 zéros\n\nt0 = time() # on stocke dans t0 le temps de départ, avant le début de la recherche\nrecherche_naive(tableau, 1)\nt1 = time() # on stocke dans t1 le temps de fin, juste après la recherche\nt1 - t0 # la différence est le temps (en SECONDES) mis par la recherche","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"raw","source":"Réponse à la question :\n\nLa durée d'exécution est approximativement multipliée par 10 (tableau à 1 millions de valeurs) et par 100 (Tableau à 10 millions de valeurs)"},{"metadata":{"trusted":true},"cell_type":"markdown","source":"# 2. Recherche par dichotomie\n## 2.1. Principe\n\n
\n\nLa liste étant **triée**, on regarde si l'élément cherché est plus petit que l'élément **central** de la liste.\n\n- Si c'est le cas on reproduit l'opération avec la première moitié de la liste, \n- sinon on reproduit l'opération avec la deuxième moitié de la liste.\n\nAinsi de suite jusqu'à trouver (ou non) l'élément recherché.\n\n
"},{"metadata":{},"cell_type":"markdown","source":"!!! info Regarder la vidéo suivante : \n[](https://www.youtube.com/embed/JdwWMnU04pQ \"Recherche dichotomique\")\n!!!"},{"metadata":{},"cell_type":"markdown","source":"Visualisation d'une recherche dichotomique, où 4 est la valeur recherchée :"},{"metadata":{"trusted":true},"cell_type":"markdown","source":""},{"metadata":{},"cell_type":"markdown","source":"## 2.2. L'algorithme"},{"metadata":{"trusted":true},"cell_type":"markdown","source":"!!! abstract L'algorithme de recherche par dichotomie (en pseudo-code ou langage naturel) :\n\nFonction recherche_dichotomique(tableau t, entier element)\n\n indice_debut ← 0\n indice_fin ← longueur(t) - 1\n \n Tant que indice_debut ⩽ indice_fin\n \n # on recherche le milieu du tableau à trier\n indice_milieu ← partie_entière((indice_début + indice_fin)/2)\n\n # si l'lément recherché se trouve au milieu du tableau, on\n # renvoie la valeur de l'indice du milieu du tableau\n \n si t[indice_milieu] = element\n renvoyer indice_milieu\n \n # si la valeur du mileu du tableau est plus grande que la valeur recherchée alors\n # la valeur recherchée est à gauche du milieu du tableau sinon il est à droite\n \n sinon si tableau{indice_milieu] > element\n indice_fin ← indice_milieu - 1\n sinon\n indice_debut ← indice_milieu + 1\n \n fin Tant que\n \n renvoyer -1\nFin Fonction\n!!!"},{"metadata":{},"cell_type":"markdown","source":"!!! question Exercice n°1\nFaire fonctionner cet algoritme sur la liste [1, 2, 3, 4, 5, 6, 7] en recherchant l'élément 2.\n\nDouble-cliquer pour compléter le tableau.\n
\n!!!"},{"metadata":{},"cell_type":"markdown","source":"!!! question Exercice n°2\nFaire fonctionner cet algoritme sur la liste [1, 2, 3, 4, 5, 6, 7, 8] en recherchant l'élément 7.\n\nDouble-cliquer pour compléter le tableau.\n
\n\nDéfinir ce qu'est l'**élément central**.\n!!!"},{"metadata":{},"cell_type":"raw","source":"Réponse :\n\nIl s'agit de la valeur de l'élément du tableau se trouvant à l'indice correspondant à la moitié du tableau, obtenu par la divison entière par 2 du nombre d'éléments dans le tableau."},{"metadata":{},"cell_type":"markdown","source":"## 2.3. Application"},{"metadata":{},"cell_type":"markdown","source":"!!! question Travail à faire\nCompléter le code de la fonction `recherche_dichotomique` ci-dessous, en vous aidant de l'algorithme ci-dessus, qui :\n- prend en paramètre une liste de nombres entiers `tableau`, triée par ordre croissant ;\n- retourne l'indice de l'élément recherché `element` dans le tableau en utilisant le recherche par dichotomie décrite dans l'algorithme ci-dessus.\n\nRédiger une *docstring* précise (entrées, sortie, précondition(s)).\n\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"def recherche_dichotomique(tableau: list, element: int) ->int:\n \"\"\"\n Condition : le tableau 'tableau' doit être trié\n Entrée : 'tableau', un tableau trié et 'element' un élment à chercher dans le tableau\n Sortie : renvoie un entier positif ou nul en cas de succès, qui correspond à une\n position de la valeur recherchée dans la tableau, et -1 en cas d’échec.\n \"\"\"\n \n gauche: int = 0\n droite: int = len(tableau) - 1\n \n while gauche <= droite:\n milieu = (gauche + droite) // 2\n if tableau[milieu] == element:\n # on a trouvé element dans le tableau, à la position milieu\n return milieu\n elif tableau[milieu] > element:\n # on cherche entre gauche et milieu - 1\n droite = milieu - 1\n else: # on a tableau[milieu] < element\n # on cherche entre milieu + 1 et droite\n gauche = milieu + 1\n # on est sorti de la boucle sans trouver element\n return -1","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"
\n\n \n**Cliquer ici pour obtenir de l'aide**\n\n\n- Préconditions : accepte-t-on une liste vide, une liste non triée ?\n- la division entière en python s'écrit `13 // 5` \n- On utilisera une structure \n```Python\nwhile contition:\n bloc d instructions a repeter\n```\n- On pourra utiliser la structure \n```Python\nif contition:\n bloc d instructions\nelif autre contition:\n bloc d instructions\nelse:\n bloc d instructions\n```\n
"},{"metadata":{},"cell_type":"markdown","source":"Réaliser ci-dessous un jeu de tests pertinant :"},{"metadata":{"trusted":false},"cell_type":"code","source":"assert recherche_dichotomique([2, 3, 4], 1) == -1, f\"([2, 3, 4], 1), attendu : -1, obtenu : {recherche_dichotomique([2, 3, 4], 1)}\"","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## 2.4. Mesure du temps d'exécution"},{"metadata":{},"cell_type":"markdown","source":"
Comme précédemment, on va prendre un tableau constitué uniquement de zéros, qui est donc trié, et y chercher la valeur 1.\n
"},{"metadata":{},"cell_type":"markdown","source":"!!! question Exercice\nMesurer le temps d'exécution de la recherche dichotomique de la valeur 1 dans ce tableau (cf. $1.3 si besoin). Pour cela, compléter le code ci-dessous :\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"from time import time\n\ntableau = [0]*10000000 # permet de créer un tableau de 10 000 000 zéros\n\n# Compléter le code ici\n\nt0 = time() # on stocke dans t0 le temps de départ, avant le début de la recherche\nrecherche_dichotomique(tableau, 1)\nt1 = time() # on stocke dans t1 le temps de fin, juste après la recherche\nt1 - t0 # la différence est le temps (en SECONDES) mis par la recherche","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"raw","source":"Durée moyenne de la recherche (en s) : ...... s"},{"metadata":{},"cell_type":"markdown","source":"## 2.5. Complexité"},{"metadata":{},"cell_type":"markdown","source":"!!! question Travail à faire\nRechercher, sur le web, la complexité temporelle (nom et notation asymptotique) de l'algorithme de recherche par dichotomie, en fonction de la taille `n` du tableau où rechercher l'élément.\n!!!"},{"metadata":{},"cell_type":"markdown","source":"Votre réponse ici :\n\nLa complexité de la recherche par dichotomie est log2(n). On obtient ainsi une complexité logarithmique."},{"metadata":{},"cell_type":"markdown","source":"# 3. Efficacité des algorithmes"},{"metadata":{},"cell_type":"markdown","source":"!!! question Travail à faire\nRécrire les fonctions `recherche_naive` et `recherche_dichotomique`, vues précédemment, en les renommant `recherche_naive_avec_compteur` et `recherche_dichotomique_avec_compteur`, en rajoutant dans le code de celles-ci un compteur (variable `compteur` par exemple) qui compte le nombre de comparaisons effectuées par la fonction et une instruction qui renvoie la valeur de ce compteur (la fonction se terminera donc par `return compteur`).\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"def recherche_naive_avec_compteur(tableau: list, element: int) ->tuple:\n \"\"\"\n Renvoie un entier positif ou nul en cas de succès, qui correspond\n à une position de la valeur recherchée dans la tableau, ainsi que\n le nombre de comparaisons et -1 en cas d’échec.\n \"\"\"\n \n compteur: int = 0\n for i in range(len(tableau)):\n compteur += 1\n if tableau[i] == element:\n return i, compteur\n return -1, compteur \n \ndef recherche_dichotomique_avec_compteur(tableau: list, element: int) ->tuple:\n \"\"\"\n condition: le tableau doit être trié\n \n Renvoie un entier positif ou nul en cas de succès, qui correspond\n à une position de la valeur recherchée dans la tableau, ainsi que\n le nombre de comparaisons et -1 en cas d’échec.\n \"\"\"\n\n compteur: int = 0\n gauche: int = 0\n droite = len(tableau) - 1\n while gauche <= droite:\n milieu = (gauche + droite) // 2\n compteur += 1\n if tableau[milieu] == element:\n # on a trouvé element dans le tableau, à la position milieu\n return milieu, compteur\n elif tableau[milieu] > element:\n # on cherche entre gauche et milieu - 1\n droite = milieu - 1\n else: # on a tableau[milieu] < element\n gauche = milieu + 1\n # on est sorti de la boucle sans trouver element\n return -1, compteur","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Vous pouvez faire des tests dans cette cellule...\ntableau = [0, 1, 2, 3, 4, 5, 6, 7, 8]\n\nprint(\"\\nRecherche naïve (avec compteur) :\\n\")\nprint(f\"L'élément recherché se trouve à l'indice : {recherche_naive_avec_compteur(tableau, 6)}\")\n\nprint(\"\\nRecherche par dichotomie (avec compteur) :\\n\")\nprint(f\"L'élément recherché se trouve à l'indice : {recherche_dichotomique_avec_compteur(tableau, 6)}\")","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"raw","source":"Que peut-on en conclure ?\n\nLa recherche par dichotomie est plus rapide : 2 comparaisons contre 7 pour la recherche naïve."},{"metadata":{"trusted":true},"cell_type":"markdown","source":"# 4. Variante"},{"metadata":{},"cell_type":"markdown","source":"!!! question Travail à faire\n\nReprendre la fonction `recherche_naive` pour qu'elle renvoie non plus l'indice de l'élément s'il est dans la liste ou `-1` s'il n'y est pas mais `True` ou `False`.\n\nFaire de même pour la fonction `recherche_dichotomique`.\n \nNe pas oublier les *docstring* ainsi que le jeu de tests.\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"def recherche_naive(tableau: list, element: int) ->bool:\n \"\"\"\n Renvoie un entier positif ou nul en cas de succès, qui correspond\n à une position de la valeur recherchée dans la tableau, et -1 en\n cas d’échec.\n \"\"\"\n \n for i in range(len(tableau)):\n if tableau[i] == element:\n return True\n return False\n \ndef recherche_dichotomique(tableau: list, element: int) ->bool:\n \"\"\"\n condition: le tableau doit être trié\n\n Renvoie un entier positif ou nul en cas de succès, qui correspond\n à une position de la valeur recherchée dans la tableau, et -1 en\n cas d’échec.\n \"\"\"\n \n gauche: int = 0\n droite: int = len(tableau) - 1\n \n while gauche <= droite:\n milieu = (gauche + droite) // 2\n if tableau[milieu] == element:\n # on a trouvé element dans le tableau, à la position milieu\n return True\n elif tableau[milieu] > element:\n # on cherche entre gauche et milieu - 1\n droite = milieu - 1\n else: # on a tableau[milieu] < element\n # on cherche entre milieu + 1 et droite\n gauche = milieu + 1\n # on est sorti de la boucle sans trouver element\n return False","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Vous pouvez faire des tests dans cette cellule...\ntableau = [0, 1, 2, 3, 4, 5, 6, 7, 8]\n\nprint(\"\\nRecherche par dichotomie (booléen):\\n\")\nprint(f\"L'élément recherché se trouve-t-il dans le tableau ? {recherche_dichotomique(tableau, 6)}\")","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"name":"python3","display_name":"Python 3","language":"python"},"celltoolbar":"Éditer les Méta-Données"},"nbformat":4,"nbformat_minor":2}