{"id":180,"date":"2020-08-24T12:05:32","date_gmt":"2020-08-24T10:05:32","guid":{"rendered":"http:\/\/maths-code.fr\/cours\/?page_id=180"},"modified":"2024-09-17T23:02:33","modified_gmt":"2024-09-17T21:02:33","slug":"recherche-dichotomique","status":"publish","type":"page","link":"https:\/\/maths-code.fr\/cours\/recherche-dichotomique\/","title":{"rendered":"Recherche dichotomique"},"content":{"rendered":"<p>Nous avons d\u00e9j\u00e0 \u00e9tudi\u00e9 des algorithmes de recherche d&rsquo;\u00e9l\u00e9ment dans un tableau : nous avions effectu\u00e9 une <em>recherche s\u00e9quentielle<\/em>. Le parcours s&rsquo;effectuait sur tout le tableau jusqu&rsquo;\u00e0 tomber sur l&rsquo;\u00e9l\u00e9ment recherch\u00e9 &#8211; s&rsquo;il y figure bien entendu. Cet algorithme est dit na\u00eff; en effet on ne cherche pas \u00e0 optimiser l&rsquo;efficacit\u00e9. Sa <em> complexit\u00e9 est lin\u00e9aire: on peut estimer que le temps de recherche double lorsque la longueur de la liste double.<\/em><br \/>\n<strong>En utilisant une liste tri\u00e9e<\/strong>, l&rsquo;algorithme de recherche dichotomique am\u00e9liore l&rsquo;efficacit\u00e9 en proc\u00e9dant comme suit :<\/p>\n<blockquote class=\"wp-block-quote\"><p>L\u2019id\u00e9e centrale de cette approche repose sur l\u2019id\u00e9e de r\u00e9duire de moiti\u00e9 l\u2019espace de recherche \u00e0 chaque \u00e9tape : on regarde la valeur du milieu et si ce n\u2019est pas celle recherch\u00e9e, on sait qu\u2019il faut continuer de chercher dans la premi\u00e8re moiti\u00e9 ou dans la seconde.<\/p><\/blockquote>\n<h3>Algorithme<\/h3>\n<p>On d\u00e9termine <em>m<\/em>, \u00e9l\u00e9ment au milieu du tableau ;<\/p>\n<ul>\n<li>si c\u2019est la valeur recherch\u00e9e, on s\u2019arr\u00eate avec un succ\u00e9s ;<\/li>\n<li>sinon, deux cas sont possibles :\n<ol>\n<li>si <em>m<\/em> est plus grand que la valeur recherch\u00e9e, comme le tableau est tri\u00e9, cela signifie qu\u2019il suffit de continuer \u00e0 chercher dans la premi\u00e8re moiti\u00e9 du tableau ;<\/li>\n<li>sinon, il suffit de chercher dans la moiti\u00e9 droite.<\/li>\n<\/ol>\n<\/li>\n<li>on r\u00e9p\u00e8te cela jusque \u00e0 avoir trouv\u00e9 la valeur recherch\u00e9, ou bien avoir r\u00e9duit l\u2019intervalle de recherche \u00e0 un intervalle vide, ce qui signifie que la valeur recherch\u00e9e n\u2019est pas pr\u00e9sente.<\/li>\n<\/ul>\n<p>\u00c0 chaque \u00e9tape, on coupe l\u2019intervalle de recherche en deux, et on en choisit une moiti\u00e9. On dit que l\u2019on proc\u00e8de par dichotomie, du grec <strong>dikha (en deux)<\/strong> et <strong>tomos (couper)<\/strong>.<\/p>\n<hr \/>\n<p>Le cours et les exercices (pdf): <a title=\"Recherche dichotomique-Cours\" href=\"http:\/\/maths-code.fr\/NSI\/1ere\/recherche_dichotomique\/recherche-dichotomique.pdf\">Recherche dichotomique-Cours<\/a><\/p>\n<hr \/>\n<p><em>Vid\u00e9o sur la recherche dichotomique avec un tableau de suivi des variables <\/em>(de la chaine \u00ab\u00a0NSI \u00e0 Mounier\u00a0\u00bb):<\/p>\n<p><iframe loading=\"lazy\" title=\"Algorithme de recherche dichotomique - Exemple\" width=\"960\" height=\"540\" src=\"https:\/\/www.youtube.com\/embed\/0vOS48RiOag?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Nous avons d\u00e9j\u00e0 \u00e9tudi\u00e9 des algorithmes de recherche d&rsquo;\u00e9l\u00e9ment dans un tableau : nous avions effectu\u00e9 une recherche s\u00e9quentielle. Le parcours s&rsquo;effectuait sur tout le tableau jusqu&rsquo;\u00e0 tomber sur l&rsquo;\u00e9l\u00e9ment recherch\u00e9 &#8211; s&rsquo;il y figure bien entendu. Cet algorithme est dit na\u00eff; en effet on ne cherche pas \u00e0 optimiser l&rsquo;efficacit\u00e9. Sa complexit\u00e9 est lin\u00e9aire: on peut estimer que le temps de recherche double lorsque la longueur de la liste double. En utilisant une liste tri\u00e9e, l&rsquo;algorithme de recherche dichotomique am\u00e9liore l&rsquo;efficacit\u00e9 en proc\u00e9dant comme suit : L\u2019id\u00e9e centrale de cette approche repose sur l\u2019id\u00e9e de r\u00e9duire de moiti\u00e9 l\u2019espace de recherche \u00e0 chaque \u00e9tape : on regarde la valeur du milieu et si ce n\u2019est pas celle recherch\u00e9e, on sait qu\u2019il faut continuer de chercher dans la premi\u00e8re moiti\u00e9 ou dans la seconde. Algorithme On d\u00e9termine m, \u00e9l\u00e9ment au milieu du tableau ; si c\u2019est la valeur recherch\u00e9e, on s\u2019arr\u00eate avec un succ\u00e9s ; sinon, deux cas sont possibles : si m est plus grand que la valeur recherch\u00e9e, comme le tableau est tri\u00e9, cela signifie qu\u2019il suffit de continuer \u00e0 chercher dans la premi\u00e8re moiti\u00e9 du tableau ; sinon, il suffit de chercher dans la moiti\u00e9 droite. on r\u00e9p\u00e8te cela jusque \u00e0 avoir trouv\u00e9 la valeur recherch\u00e9, ou bien avoir r\u00e9duit l\u2019intervalle de recherche \u00e0 un intervalle vide, ce qui signifie que la valeur recherch\u00e9e n\u2019est pas pr\u00e9sente. \u00c0 chaque \u00e9tape, on coupe l\u2019intervalle de recherche en deux, et on en choisit une moiti\u00e9. On dit que l\u2019on proc\u00e8de par dichotomie, du grec dikha (en deux) et tomos (couper). Le cours et les exercices (pdf): Recherche dichotomique-Cours Vid\u00e9o sur la recherche dichotomique avec un tableau de suivi des variables (de la chaine \u00ab\u00a0NSI \u00e0 Mounier\u00a0\u00bb):<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"class_list":["post-180","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/pages\/180","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/comments?post=180"}],"version-history":[{"count":27,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/pages\/180\/revisions"}],"predecessor-version":[{"id":5927,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/pages\/180\/revisions\/5927"}],"wp:attachment":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/media?parent=180"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}