{"id":1625,"date":"2022-05-03T10:25:15","date_gmt":"2022-05-03T08:25:15","guid":{"rendered":"https:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/?p=1625"},"modified":"2022-05-03T11:17:06","modified_gmt":"2022-05-03T09:17:06","slug":"dichotomie","status":"publish","type":"post","link":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/2022\/05\/03\/dichotomie\/","title":{"rendered":"Dichotomie"},"content":{"rendered":"\n

https:\/\/colab.research.google.com\/drive\/1zuM0K-AIPZoLF7xCL1vBT2uhOlPjdMeW#scrollTo=Asrq-pcaUD8N&uniqifier=1<\/a><\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n
\"\"
temps d’ex\u00e9cution longs pour 10 000 000 et 9 999 999<\/figcaption><\/figure>\n\n\n\n

Recherche s\u00e9quentielle<\/strong><\/p>\n\n\n\n

Ecriture d’une fonction qui recherche une valeur val dans un tableau tab. La fonction doit renvoyer True si la valeur est pr\u00e9sente, False si elle est absente.<\/p>\n\n\n\n

Test :<\/p>\n\n\n\n

def rechercher(tab,val):\n  for x in tab:\n    if val == x:\n      return True\n  return False<\/pre>\n\n\n\n
Correction :<\/p>\n\n\n\n
–> Cet algorithme n’est pas optimal puisque l’on doit passer par chaque valeur pour trouver la bonne, alors qu’elles sont d\u00e9j\u00e0 tri\u00e9es. Cela aurait \u00e9t\u00e9 plus pertinent si les valeurs \u00e9taient d\u00e9j\u00e0 tri\u00e9es.<\/p>\n\n\n\n
<\/p>\n\n\n\n
def rechercher(tab,val):\n    for nombre in tab:\n        if nombre==val:\n            return True\n    return False   <\/pre>\n\n\n\n
Re<\/strong>cherche dichotomique<\/strong><\/p>\n\n\n\n
Test :<\/p>\n\n\n\n
–> Par exemple, une personne pense \u00e0 un nombre entre 0 et 100 :<\/p>\n\n\n\n
On va demander si ce nombre correspond \u00e0 50, et la personne va nous dire si c’est plus ou moins (ou 50, dans ces cas-l\u00e0 l’algorithme s’arr\u00eate l\u00e0).<\/p>\n\n\n\n
Si le nombre est sup\u00e9rieur :<\/p>\n\n\n\n
  • on va demander le milieu de 100 et 50, autrement dit (100 + 50) \/\/ 2 = 75<\/li><\/ul>\n\n\n\n
    Si le nombre est inf\u00e9rieur :<\/p>\n\n\n\n
    • on va simplement demander la moiti\u00e9 de 50, c’est-\u00e0-dire 50 \/\/ 2 =25<\/li><\/ul>\n\n\n\n
      Et ainsi de suite jusqu’\u00e0 trouver le \u00ab\u00a0juste prix\u00a0\u00bb !<\/p>\n\n\n\n
      def dichotomie(tab,val):\n  d\u00e9but = tab(0)\n  if m>d\u00e9but:\n    d\u00e9but = (len(tab)+d\u00e9but)\/\/2\n  elif m>d\u00e9but:\n    d\u00e9but = d\u00e9but\/\/2\n  else:\n    return True<\/pre>\n\n\n\n
      Correction :<\/p>\n\n\n\n
      –> Tant que le nombre de d\u00e9part est inf\u00e9rieur ou \u00e9gal au nombre de fin :<\/p>\n\n\n\n
      • le nombre que l’on cherche est \u00e9gal au (nombre de d\u00e9part + celui de fin) \/\/ 2<\/li>
      • ainsi si la valeur que l’on cherche est \u00e9gale \u00e0 m dans tab, le programme s’arr\u00eate et renvoie True<\/li>
      • si valeur que l’on cherche est sup\u00e9rieure \u00e0 m dans tab, le nombre de d\u00e9part devient m + 1<\/li>
      • sinon, le nombre de fin devient m – 1<\/li><\/ul>\n\n\n\n
        etc, jusqu’\u00e0 ce que le programme tombe sur le nombre ou renvoie False.<\/p>\n\n\n\n
        def dichotomie(tab,val):\n    debut = 0\n    fin = len(tab) - 1\n    while debut <= fin:\n        m = (debut + fin) \/\/ 2\n        if val== tab[m]:\n            return True\n        if val > tab[m]:\n            debut = m + 1\n        else:\n            fin = m - 1\n    return False<\/pre>\n\n\n\n
        Comparaison<\/strong><\/p>\n\n\n\n
        Tests :<\/p>\n\n\n\n
        tab = [i for i in range(100000000)]<\/pre>\n\n\n\n
        rechercher(tab,99999999)<\/pre>\n\n\n\n
        import timeit\ntab = [i for i in range(1000000)]\n%timeit rechercher(tab,999999)<\/pre>\n\n\n\n
        Correction :<\/p>\n\n\n\n
        import time\ntab=[i for i in range(100000000)]\ndebut1=time.time()\nrechercher(tab,10000000)\nduree1=time.time()-debut1\nprint(duree1)\ndebut2=time.time()\ndichotomie(tab,10000000)\nduree2=time.time()-debut2\nprint(duree2)<\/pre>\n\n\n\n
        <\/p>\n","protected":false},"excerpt":{"rendered":"
        https:\/\/colab.research.google.com\/drive\/1zuM0K-AIPZoLF7xCL1vBT2uhOlPjdMeW#scrollTo=Asrq-pcaUD8N&uniqifier=1 Recherche s\u00e9quentielle Ecriture d’une fonction qui recherche une valeur val dans un tableau tab. La fonction doit renvoyer True si la valeur est pr\u00e9sente, False si elle est absente. Test : Correction : –> Cet algorithme n’est pas optimal puisque l’on doit passer par chaque valeur pour trouver la bonne, alors qu’elles sont d\u00e9j\u00e0 […]<\/p>\n","protected":false},"author":4,"featured_media":1647,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/posts\/1625"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/comments?post=1625"}],"version-history":[{"count":25,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/posts\/1625\/revisions"}],"predecessor-version":[{"id":1658,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/posts\/1625\/revisions\/1658"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/media\/1647"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/media?parent=1625"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/categories?post=1625"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/tags?post=1625"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}