{"id":287,"date":"2022-05-12T02:59:40","date_gmt":"2022-05-12T00:59:40","guid":{"rendered":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/?p=287"},"modified":"2022-05-12T02:59:40","modified_gmt":"2022-05-12T00:59:40","slug":"recherche-dichotomique","status":"publish","type":"post","link":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/2022\/05\/12\/recherche-dichotomique\/","title":{"rendered":"Recherche dichotomique"},"content":{"rendered":"\n<p class=\"has-light-green-cyan-background-color has-background\">La recherche par dichotomie ou commun\u00e9ment appel\u00e9 recherche dichotomique est un algorithme qui nous permet de trouver la position pr\u00e9cise d&rsquo;un \u00e9l\u00e9ment pr\u00e9sent dans un tableau tri\u00e9. Cet algorithme va comparer l&rsquo;\u00e9l\u00e9ment avec la valeur de la case pr\u00e9sente 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>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"630\" height=\"102\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-content\/uploads\/sites\/15\/2022\/05\/image-9.png\" alt=\"\" class=\"wp-image-288\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-content\/uploads\/sites\/15\/2022\/05\/image-9.png 630w, http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-content\/uploads\/sites\/15\/2022\/05\/image-9-300x49.png 300w\" sizes=\"(max-width: 630px) 100vw, 630px\" \/><\/figure>\n\n\n\n<p class=\"has-medium-font-size\">Par exemple, <\/p>\n\n\n\n<p>A et B jouent au jeu suivant&nbsp;: A choisit un nombre entre 1 et 20, et ne le communique pas \u00e0 B, B doit trouver ce nombre en posant des questions \u00e0 A dont les r\u00e9ponses ne peuvent \u00eatre que \u00ab&nbsp;Non, plus grand&nbsp;\u00bb, \u00ab&nbsp;Non, plus petit&nbsp;\u00bb ou \u00ab&nbsp;Oui, trouv\u00e9&nbsp;\u00bb. B doit essayer de poser le moins de questions possible.<\/p>\n\n\n\n<p class=\"has-vivid-red-color has-text-color\">Une strat\u00e9gie pour B est d&rsquo;essayer tous les nombres, mais il peut aller plus rapidement comme le montre le sc\u00e9nario suivant&nbsp;:<\/p>\n\n\n\n<p class=\"has-vivid-red-color has-text-color\">A choisit 14 et attend les questions de B&nbsp;:<\/p>\n\n\n\n<ul class=\"has-light-green-cyan-background-color has-background\"><li>B sait que le nombre est entre 1 et 20\u00a0; au milieu se trouve 10 (ou 11), B demande donc\u00a0: \u00ab\u00a0Est-ce que le nombre est 10\u00a0?\u00a0\u00bb. A r\u00e9pond \u00ab\u00a0Non, plus grand\u00a0\u00bb.<\/li><li>B sait maintenant que le nombre est entre 11 et 20\u00a0; au milieu se trouve 15 (ou 16), il demande donc\u00a0: \u00ab\u00a0Est-ce que le nombre est 15\u00a0?\u00a0\u00bb A r\u00e9pond \u00ab\u00a0Non, plus petit\u00a0\u00bb<\/li><li>Et ainsi de suite\u00a0: \u00ab\u00a0Est-ce 12\u00a0?\u00a0\u00bb (12 &lt; 12,5 &lt; 13), \u00ab\u00a0Non, plus grand\u00a0\u00bb, \u00ab\u00a0Est-ce 13?\u00a0\u00bb (13 &lt; 13,5 &lt; 14), \u00ab\u00a0Non, plus grand\u00a0\u00bb, \u00ab\u00a0Est-ce bien 14\u00a0?\u00a0\u00bb, \u00ab\u00a0Oui, trouv\u00e9\u00a0\u00bb<\/li><li>B a trouv\u00e9 le nombre choisi par A en seulement 5 questions.<\/li><\/ul>\n\n\n\n<p>Il y a deux types de recherches, l&rsquo;une o\u00f9 cela se passe dans une s\u00e9quence et l&rsquo;autre se passe dans un tableau avec d&rsquo;innombrables valeurs :<\/p>\n\n\n\n<ul><li>Recherche S\u00e9quentielle<\/li><li>Recherche Dichotomique <\/li><\/ul>\n\n\n\n<p class=\"has-light-green-cyan-background-color has-background\">Recherche s\u00e9quentielle<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def rechercher(tab,val):\n    for nombre in tab:\n        if nombre==val:\n            return True\n    return False   <\/pre>\n\n\n\n<p class=\"has-light-green-cyan-background-color has-background\">Recherche dichotomique<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def dichotomie(tab,val):\n    debut = 0\n    fin = len(tab) - 1\n    while debut &lt;= fin:\n        m = (debut + fin) \/\/ 2\n        if val== tab[m]:\n            return True\n        if val &gt; tab[m]:\n            debut = m + 1\n        else:\n            fin = m - 1\n    return False<\/pre>\n\n\n\n<p>Mais nous pouvons aussi comparer toutes les valeurs pr\u00e9sentes gr\u00e2ce \u00e0 la comparaison :<\/p>\n\n\n\n<p class=\"has-light-green-cyan-background-color has-background\">Comparaison <\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">import time\n\ntab=[i for i in range(100000000)]\n\ndebut1=time.time()\nrechercher(tab,10000000)\nduree1=time.time()-debut1\nprint(duree1)\n\ndebut2=time.time()\ndichotomie(tab,10000000)\nduree2=time.time()-debut2\nprint(duree2)<\/pre>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>La recherche par dichotomie ou commun\u00e9ment appel\u00e9 recherche dichotomique est un algorithme qui nous permet de trouver la position pr\u00e9cise d&rsquo;un \u00e9l\u00e9ment pr\u00e9sent dans un tableau tri\u00e9. Cet algorithme va comparer l&rsquo;\u00e9l\u00e9ment avec la valeur de la case pr\u00e9sente au milieu du tableau : si les valeurs sont \u00e9gales, la t\u00e2che est accomplie sinon on [&hellip;]<\/p>\n","protected":false},"author":13,"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\/maxence\/wp-json\/wp\/v2\/posts\/287"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/users\/13"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/comments?post=287"}],"version-history":[{"count":1,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/posts\/287\/revisions"}],"predecessor-version":[{"id":289,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/posts\/287\/revisions\/289"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/media?parent=287"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/categories?post=287"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/tags?post=287"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}