{"id":1232,"date":"2020-06-11T14:03:36","date_gmt":"2020-06-11T12:03:36","guid":{"rendered":"http:\/\/labodemaths.fr\/WordPress3\/?p=1232"},"modified":"2020-09-09T19:16:53","modified_gmt":"2020-09-09T17:16:53","slug":"recherche-par-dichotomie","status":"publish","type":"post","link":"https:\/\/labodemaths.fr\/WordPress3\/recherche-par-dichotomie\/","title":{"rendered":"Recherche par dichotomie"},"content":{"rendered":"\n

La recherche dichotomique<\/strong>, ou recherche par dichotomie<\/strong>1<\/a><\/sup> (en anglais<\/a> : binary search<\/em>), est un algorithme de recherche<\/a> pour trouver la position d’un \u00e9l\u00e9ment dans un tableau<\/a> tri\u00e9.<\/p>

Le principe est le suivant : comparer l’\u00e9l\u00e9ment avec la valeur de la case au milieu du tableau ; si les valeurs sont \u00e9gales, la t\u00e2che est accomplie, sinon on recommence dans la moiti\u00e9 du tableau pertinente.<\/p>https:\/\/fr.wikipedia.org\/wiki\/Recherche_dichotomique#:~:text=La%20recherche%20dichotomique%2C%20ou%20recherche,%C3%A9l%C3%A9ment%20dans%20un%20tableau%20tri%C3%A9.&text=Le%20nombre%20d’it%C3%A9rations%20de,en%20la%20taille%20du%20tableau.<\/a><\/cite><\/blockquote>\n\n\n\n

Etape 1<\/h2>\n\n\n\n

Ecrire une fonction liste_hasard(n,p) permettant de g\u00e9n\u00e9rer al\u00e9atoirement une liste de n nombres entiers diff\u00e9rents compris entre 0 et p. On aura naturellement p>n.<\/p>\n\n\n\n

Exemple : <\/p>\n\n\n\n

>>> liste_hasard(10,100)\n[54, 60, 46, 20, 64, 96, 39, 42, 51, 91]<\/code><\/pre>\n\n\n\n
Etape 2<\/h3>\n\n\n\n
On consid\u00e8re une liste de nombres diff\u00e9rents et tri\u00e9s.
En utilisant le principe de recherche par dichotomie, \u00e9crire une fonction permettant de d\u00e9terminer si un nombre appartient \u00e0 cette liste et de pr\u00e9ciser alors son indice ou d’indiquer qu’il n’appartient pas \u00e0 cette liste.<\/p>\n\n\n\n
Travail \u00e0 finir :<\/p>\n\n\n\n
from random import randint\n\ndef liste_hasard(n,p):\n    liste=[]\n    while len(liste)<n+1 :\n        nbre=randint(0,p)\n        if not(nbre in liste):\n            liste.append(nbre)\n    liste.sort()\n    return liste\n\ndef dichotomie(x,liste):\n    l=liste.copy()\n    while len(liste)!=1 :\n        print()\n        print(liste)\n        i_milieu=int(len(liste)\/2)\n        if x in liste[0:i_milieu]:\n            liste=liste[0:i_milieu]\n        else :\n            liste=liste[i_milieu:len(liste)]\n        \n    return liste\n\nliste=[i for i in range(0,100)]\nprint(liste)\nprint(dichotomie(68,liste))\n       <\/code><\/pre>\n\n\n\n
Proposition de correction pour des listes rang\u00e9es ou non rang\u00e9es.
L’algorithme est plus efficace en co\u00fbt et en rapidit\u00e9 pour une liste rang\u00e9e.<\/p>\n\n\n\n
from random import randint\n\ndef liste_hasard(n,p):\n    '''\n    n,p : entiers naturels avec n<p\n    return : liste de longueur n contenant des nbres entiers\n             diff\u00e9rents compris entre 0 et p\n    >>> a=liste_hasard(10,50)\n    >>> a\n    [14, 42, 15, 1, 16, 34, 4, 37, 22, 11]\n    '''\n    liste=[]\n    for i in range(n):\n        arret=True\n        while arret:\n            x=randint(0,p)\n            if x in liste:\n                arret=True\n            else :\n                arret=False\n                liste.append(x)\n    return liste\n\ndef dichotomie_non_rangee(l,val):\n    '''\n    l : liste non rang\u00e9e de nombres \n    val : un nombre entier\n    return : l'indice correspondant \u00e0 val dans la liste l si val appartient \u00e0 la liste et False sinon\n    >>> a=[32, 2, 37, 0, 45, 25, 3, 36, 8, 9] \n    >>> dichotomie_non_rangee(a,32)\n    0\n    >>> dichotomie_non_rangee(a,9)\n    9\n    >>> dichotomie_non_rangee(a,1)\n    False\n    >>> \n    '''\n    liste=l\n    min=0\n    max=len(liste)-1\n    while max-min!=1:\n        pivot=int((max+min)\/2)\n        if val in liste[min:pivot]:\n            max=pivot\n        else :\n            min=pivot\n    if l[max]==val:\n        return max\n    if l[min]==val:\n        return min\n    return False\n\ndef dichotomie_rangee(l,val):\n    '''\n    l : liste rang\u00e9e de nombres\n    val : un nombre entier\n    return : l'indice correspondant \u00e0 val dans la liste l si val appartient \u00e0 la liste et False sinon\n    >>> a=[32, 2, 37, 0, 45, 25, 3, 36, 8, 9]\n    >>> a.sort()\n    >>> a\n    [0, 2, 3, 8, 9, 25, 32, 36, 37, 45]\n    >>> dichotomie_rangee(a,0)\n    0\n    >>> dichotomie_rangee(a,45)\n    9\n    >>> dichotomie_rangee(a,1)\n    False\n    '''\n    liste=l\n    min=0\n    max=len(liste)-1\n    while max-min!=1:\n        pivot=int((max+min)\/2)\n        if val <liste[pivot]:\n            max=pivot\n        else :\n            min=pivot\n    if liste[max]==val:\n        return max\n    if liste[min]==val:\n        return min\n    return False\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
La recherche dichotomique, ou recherche par dichotomie1 (en anglais : binary search), est un algorithme de recherche pour trouver la position d’un \u00e9l\u00e9ment…<\/p>\n
Read the postRecherche par dichotomie<\/span><\/a><\/div>\n","protected":false},"author":2,"featured_media":1233,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/1232"}],"collection":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/comments?post=1232"}],"version-history":[{"count":8,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/1232\/revisions"}],"predecessor-version":[{"id":1262,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/1232\/revisions\/1262"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/media\/1233"}],"wp:attachment":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/media?parent=1232"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/categories?post=1232"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/tags?post=1232"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}