{"id":196,"date":"2022-05-07T10:31:00","date_gmt":"2022-05-07T08:31:00","guid":{"rendered":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/?p=196"},"modified":"2022-05-09T17:22:18","modified_gmt":"2022-05-09T15:22:18","slug":"recherche-dichotomique-dans-un-tableau-trie","status":"publish","type":"post","link":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/2022\/05\/07\/recherche-dichotomique-dans-un-tableau-trie\/","title":{"rendered":"Recherche dichotomique dans un tableau tri\u00e9"},"content":{"rendered":"\n<p>La\u00a0recherche dichotomique est un\u00a0algorithme de recherche\u00a0pour trouver la position d&rsquo;un \u00e9l\u00e9ment dans un\u00a0tableau\u00a0tri\u00e9. Le principe est le suivant\u00a0: comparer l&rsquo;\u00e9l\u00e9ment avec la valeur de la case au milieu du tableau\u00a0; 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<p>Le nombre de comparaisons, est\u00a0logarithmique\u00a0en la taille du tableau. Il y a de nombreuses structures sp\u00e9cialis\u00e9es (comme les\u00a0tables de hachage) qui peuvent \u00eatre recherch\u00e9es plus rapidement, mais la recherche dichotomique s&rsquo;applique \u00e0 plus de probl\u00e8mes.<\/p>\n\n\n\n<p>La dichotomie poss\u00e8de une\u00a0complexit\u00e9 algorithmique\u00a0logarithmique en le nombre d&rsquo;\u00e9l\u00e9ments composant le tableau dans lequel s&rsquo;effectue la recherche.<\/p>\n\n\n\n<p>On consid\u00e8re dans un premier temps le nombre de comparaisons comme \u00e9tant la mesure de complexit\u00e9. On appelle\u00a0T(n)\u00a0le nombre de comparaisons effectu\u00e9es pour une instance de taille\u00a0n. Alors le nombre de comparaisons\u00a0<em>T<\/em>\u00a0satisfait la r\u00e9currence suivante\u00a0:\u00a0T(n)=1+T(n\/2). D&rsquo;apr\u00e8s le\u00a0\u00ab\u00a0master theorem\u00a0\u00bb, cette r\u00e9currence a une solution de la forme\u00a0T(n)=O(log(n)), avec la\u00a0notation de Landau. Enfin le nombre de comparaisons est lin\u00e9aire en le nombre d&rsquo;op\u00e9rations effectu\u00e9es; l&rsquo;algorithme a donc une complexit\u00e9 logarithmique.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>La\u00a0recherche dichotomique est un\u00a0algorithme de recherche\u00a0pour trouver la position d&rsquo;un \u00e9l\u00e9ment dans un\u00a0tableau\u00a0tri\u00e9. Le principe est le suivant\u00a0: comparer l&rsquo;\u00e9l\u00e9ment avec la valeur de la case au milieu du tableau\u00a0; si les valeurs sont \u00e9gales, la t\u00e2che est accomplie, sinon on recommence dans la moiti\u00e9 du tableau pertinente. Le nombre de comparaisons, est\u00a0logarithmique\u00a0en la taille [&hellip;]<\/p>\n","protected":false},"author":10,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[],"_links":{"self":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/posts\/196"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/users\/10"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/comments?post=196"}],"version-history":[{"count":1,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/posts\/196\/revisions"}],"predecessor-version":[{"id":197,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/posts\/196\/revisions\/197"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/media?parent=196"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/categories?post=196"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/tags?post=196"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}