{"id":280,"date":"2022-05-02T17:22:24","date_gmt":"2022-05-02T15:22:24","guid":{"rendered":"http:\/\/yb-isn.fr\/2021\/nsi\/olga\/?p=280"},"modified":"2022-05-03T11:07:31","modified_gmt":"2022-05-03T09:07:31","slug":"dichotomie","status":"publish","type":"post","link":"http:\/\/yb-isn.fr\/2021\/nsi\/olga\/2022\/05\/02\/dichotomie\/","title":{"rendered":"Recherche dichotomique dans un tableau tri\u00e9"},"content":{"rendered":"\n<p><a href=\"https:\/\/colab.research.google.com\/drive\/1Gbz25OVKrGYRu6A5G-LmRzZ7sCKV4i2P?usp=sharing\">https:\/\/colab.research.google.com\/drive\/1Gbz25OVKrGYRu6A5G-LmRzZ7sCKV4i2P?usp=sharing<\/a><\/p>\n\n\n\n<p>Nous allons d&rsquo;abord faire une fonction qui permet de chercher une valeur dans une table et si une valeur n&rsquo;est pas inclus dans la table, alors la fonction est fausse<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>def recherche(tab,val):\n  for nombre in tab:\n    if nombre==val:\n      return True\n    return False<\/code><\/pre>\n\n\n\n<p>Une recherche dichotomique permet de trouver une valeur en divisant la table par deux. par exemple je cherche un nombre entre 1 et 100, je pense \u00e0 25. 25 est plus petit que le milieu de 100, donc on divise encore par 2 et nous avons trouv\u00e9 le nombre. <\/p>\n\n\n\n<p>Nous allons faire une fonction dichotomique <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>def recherche(tab,val):\n  for nombre in tab:\n    if nombre==val:\n      return True\n    return False<\/code><\/pre>\n\n\n\n<p>Nous allons ensuite comparer le temps que prend la machine si jamais on lui demande de chercher un nombre dans une liste<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>import time\ntab=&#091;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)<\/code><\/pre>\n\n\n\n<p>Nous remarquons que la machine ne peut pas supporter cette comparaison car la table est bcp trop grande<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"654\" height=\"501\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/olga\/wp-content\/uploads\/sites\/2\/2022\/05\/image.png\" alt=\"\" class=\"wp-image-283\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/olga\/wp-content\/uploads\/sites\/2\/2022\/05\/image.png 654w, http:\/\/yb-isn.fr\/2021\/nsi\/olga\/wp-content\/uploads\/sites\/2\/2022\/05\/image-300x230.png 300w\" sizes=\"(max-width: 654px) 100vw, 654px\" \/><\/figure>\n\n\n\n<p>ln est une variable qui permet de chercher la puissance de deux par exemple pour diviser un entier <\/p>\n\n\n\n<p>ex: ln(2048)\/ln(2) = 11 le r\u00e9sultat est la puissance de 2<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/colab.research.google.com\/drive\/1Gbz25OVKrGYRu6A5G-LmRzZ7sCKV4i2P?usp=sharing Nous allons d&rsquo;abord faire une fonction qui permet de chercher une valeur dans une table et si une valeur n&rsquo;est pas inclus dans la table, alors la fonction est fausse Une recherche dichotomique permet de trouver une valeur en divisant la table par deux. par exemple je cherche un nombre entre 1 et 100,&hellip; <a class=\"more-link\" href=\"http:\/\/yb-isn.fr\/2021\/nsi\/olga\/2022\/05\/02\/dichotomie\/\">Poursuivre la lecture <span class=\"screen-reader-text\">Recherche dichotomique dans un tableau tri\u00e9<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/olga\/wp-json\/wp\/v2\/posts\/280"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/olga\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/olga\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/olga\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/olga\/wp-json\/wp\/v2\/comments?post=280"}],"version-history":[{"count":6,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/olga\/wp-json\/wp\/v2\/posts\/280\/revisions"}],"predecessor-version":[{"id":288,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/olga\/wp-json\/wp\/v2\/posts\/280\/revisions\/288"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/olga\/wp-json\/wp\/v2\/media?parent=280"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/olga\/wp-json\/wp\/v2\/categories?post=280"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/olga\/wp-json\/wp\/v2\/tags?post=280"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}