{"id":301,"date":"2022-05-03T10:40:30","date_gmt":"2022-05-03T08:40:30","guid":{"rendered":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/?p=301"},"modified":"2022-05-10T23:10:01","modified_gmt":"2022-05-10T21:10:01","slug":"recherche-dichotomique-dans-un-tableau-trie","status":"publish","type":"post","link":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/2022\/05\/03\/recherche-dichotomique-dans-un-tableau-trie\/","title":{"rendered":"Recherche dichotomique dans un tableau tri\u00e9"},"content":{"rendered":"\n
\"\"<\/figure>\n\n\n\n

https:\/\/colab.research.google.com\/drive\/1U5xi-XDZd0nLkbX6hyPg9KE9XlZjoH9o?usp=sharing<\/a><\/p>\n\n\n\n

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

Nous allons d\u2019abord commencer \u00e0 faire une fonction qui permet de chercher une valeur dans une liste et si une valeur est inclus dans la liste alors la fonction True sinon False . <\/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
\"\"<\/figure>\n\n\n\n
  II| Recherche<\/em>\u00a0d<\/em>ichotomique<\/strong><\/p>\n\n\n\n
Elle va nous permettre de trouver une valeur en divisant la table par deux. par exemple je cherche un nombre entre 0 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
Test :<\/p>\n\n\n\n
\u2013> 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\u2019est plus ou moins (ou 50, dans ces cas-l\u00e0 l\u2019algorithme s\u2019arr\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\u2019est-\u00e0-dire 50 \/\/ 2 =25<\/li><\/ul>\n\n\n\n
      Et ainsi de suite jusqu\u2019\u00e0 trouver le \u00ab juste prix \u00bb !<\/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
      III |<\/strong> Comparaison<\/strong><\/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\n\n\n
      <\/p>\n\n\n\n
      <\/p>\n\n\n\n
      <\/p>\n\n\n\n
      <\/p>\n\n\n\n
      <\/p>\n\n\n\n
      <\/p>\n\n\n\n
      <\/p>\n\n\n\n
      <\/p>\n\n\n\n
      <\/p>\n\n\n\n
      <\/p>\n\n\n\n
      <\/p>\n","protected":false},"excerpt":{"rendered":"
      https:\/\/colab.research.google.com\/drive\/1U5xi-XDZd0nLkbX6hyPg9KE9XlZjoH9o?usp=sharing I| Recherche s\u00e9quentielle Nous allons d\u2019abord commencer \u00e0 faire une fonction qui permet de chercher une valeur dans une liste et si une valeur est inclus dans la liste alors la fonction True sinon False . II| Recherche\u00a0dichotomique Elle va nous permettre de trouver une valeur en divisant la table par deux. par exemple […]<\/p>\n","protected":false},"author":3,"featured_media":302,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/posts\/301"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/comments?post=301"}],"version-history":[{"count":6,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/posts\/301\/revisions"}],"predecessor-version":[{"id":339,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/posts\/301\/revisions\/339"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/media\/302"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/media?parent=301"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/categories?post=301"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/zakaria\/wp-json\/wp\/v2\/tags?post=301"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}