{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.algo - Recherche dichotomique\n", "\n", "Recherche dichotomique illustr\u00e9e. Extrait de [Recherche dichotomique, r\u00e9cursive, it\u00e9rative et le logarithme](http://www.xavierdupre.fr/blog/2013-12-01_nojs.html)."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["
run previous cell, wait for 2 seconds
\n", ""], "text/plain": [""]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Lorsqu'on d\u00e9crit n'importe quel algorithme, on \u00e9voque toujours son co\u00fbt, souvent une formule de ce style :\n", "\n", "$$O(n^u(\\ln_2 n)^v)$$\n", "\n", "$u$ et $v$ sont des entiers. $v$ est souvent soit 0, soit 1. Mais d'o\u00f9 vient ce logarithme ? Le premier algorithme auquel on pense et dont le co\u00fbt correspond au cas $u=0$ et $v=1$ est la recherche dichotomique. Il consiste \u00e0 chercher un \u00e9l\u00e9ment dans une liste tri\u00e9e. Le logarithme vient du fait qu'on r\u00e9duit l'espace de recherche par deux \u00e0 chaque it\u00e9ration. Fatalement, on trouve tr\u00e8s vite l'\u00e9l\u00e9ment \u00e0 chercher. Et le logarithme, dans la plupart des algorithmes, vient du fait qu'on divise la dimension du probl\u00e8me par un nombre entier \u00e0 chaque it\u00e9ration, ici 2.\n", "\n", "La recherche dichotomique est assez simple : on part d'une liste tri\u00e9e ``T`` et on cherche l'\u00e9l\u00e9ment ``v`` (on suppose qu'il s'y trouve). On proc\u00e8de comme suit :\n", "\n", "* On compare ``v`` \u00e0 l'\u00e9l\u00e9ment du milieu de la liste.\n", "* S'il est \u00e9gal \u00e0 ``v``, on a fini.\n", "* Sinon, s'il est inf\u00e9rieur, il faut chercher dans la premi\u00e8re moiti\u00e9 de la liste. On retourne \u00e0 l'\u00e9tape 1 avec la liste r\u00e9duite.\n", "* S'il est sup\u00e9rieur, on fait de m\u00eame avec la seconde moiti\u00e9 de la liste.\n", "\n", "C'est ce qu'illustre la figure suivante o\u00f9 ``a`` d\u00e9signe le d\u00e9but de la liste, ``b`` la fin, ``m`` le milieu. A chaque it\u00e9ration, on d\u00e9place ces trois positions."]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [{"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAWcAAAEaCAIAAABCZgHFAAAAAXNSR0IArs4c6QAAAARnQU1BAACx\njwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAACwSSURBVHhe7Z0JeEzX28BvNomEiCyWIBsS1E6s\nRZSqfU/rX5RaGkLRoi2frVotimpRWmprUVtCraVqidhjX2LfEpFEEtnXmfc7b+4VRDKZTGYm5968\nv2eePnXuzZzk3rm/Oec957xHAIIgiMJA1iAIonCQNQiCKBxkDYIgCgdZgyCIwkHWIAiicJA1CIIo\nHEayRlRU1IwZM1xcXMobmNq1a69atUqqlVAQarV606ZNXl5e0p02GG5ubl999VVkZKRUMfEGRrLG\nnj17ypYtKxgFS0tLqVZCQWRmZjo4OEj32MBYWFgcPXpUqph4AyNZIyAgQLwf7u7uDQ2GnZ2dWItU\nK6EgmDXEm1u6dOlKBqNcuXJiLYcPH5YqJt7A2Nb4+++/pSID4OvrK9Yi/ZtQEDnWaNKkyUyD0bt3\nb7EWsoYGyBqEPCBr8ANZg5AHZA1+IGsQ8oCswQ9kDUIekDX4gaxByAOyBj+QNQh5QNbgB7IGIQ/I\nGvxA1iDkAVmDH8gahDwga/ADWYOQB2QNfiBrEPKArMEPeT1gkQfG+zT3zKHTkJ//eyAd0hWyBlFE\nyBr8kPsBizo0v91bDqYm4qXLxsTE1K3bgn03UqRTdIGsQRQRsgY/5H7AngUt69229/zjT9T4r8wn\nl7cMrWMuCM4Dvt/9ODn7jFxkZMDOnXDuHKSnSyV5QdYgighZgx/yfMASHpw9FXQM+Tdg9eh3q7KL\n6PP52psx0uHXuH0bWrcGe3tYtQqioqTCNyBrEEWErMEPuR+w1Iir+3d816ui3at9FEa+1khOhl9+\ngfr1wcoKPvsMbtwAlUo69ApkDaKIkDX4IdcDFnvip1F1Ha0EoXKnMdNmzJgxZcInHevZs4uYrzUY\nWVnwzz/QuTOUKQN9+wK73Kzb8jpkDaKIkDX44fUHLOnSz4PaOrJr1mzS5TiMbKSEXZg/sAYr0GQN\nkatXYexYKF8emjeHTZsgKUkqz4asQRQRsgY/vP6AxZ6Z+35LzL1ZYfSJLBWkJ5xfO86jYmlWULA1\nGBER8MMPUKUKuLvD/Pnw/LlUTtYgigxZgx9ef8BUaad/HVKvErtoNhXc3NxcXSqVtxYvolbWYLAm\nxl9/QZ06ULYs+PlBXJxYTNYgighZgx/yeMDCAya4OZU2QcrWa/bZ3PkDXUxM2k9cp5U1RE6cwH6K\nqSk0bQpPn7ICsgZRRMga/GCwB+zePYyM2tiAiwscOBCwYYN4M8gahG6QNfjBkA9YfDxMnAjOzux1\nsHv3ioJgQtYgdIWswQ8GfsAyMnD2V8OG0aamPwpCLUHYQ9YgdIKswQ+Gf8CyslgPJbNLl2eCsE0Q\nbq1e/eZsDn1B1lAwZA1+MMoDlpkZsm7dckGIFoQsb2/YvBlVYgDIGgqGrMEPRnrAdgQEOAvCVEGI\nMDGBatXgu+80r3bTDbKGgiFr8IORHjBx5LW0IOwbMgStYW0NAwZAbKx0WE+QNRQMWYMfjGoNxvbt\n29POnk13dVWbmkLr1qqrVzPS9Ebfvn3FWqRaCQWRY41GjRpNMxg9e/YUayFraMDY1hBxEIRAQYgX\nhAuC0EsQpPmn+kOqlVAQOdYwDmQNDRjpAQsMZJZ4DVtBmC0IjwThtiCME4QK2bM59IVUK6EgmDVM\nTPT4GSkAsoYGjN3W6Nq1q/8LvvD3Dxo2TNWw4TNz86WWlmM7d/YfPVo6phPVq1cXa5FqJRRETlvD\nycnJ22C4u7uLtZA1NGBsa+SeG5qSgrk5unQBOzvo1w+Cg6VynaBoqIKhaCg/FLc1GJmZcOkSjByJ\ny2QbNYI//8QSnSBrKBiyBj9wYA2GWo1LY+fOhdKlcVx21ixITJQOFQayhoIha/ADH9YQSUuDAwfA\n0REzCQ4fDuHhUrnWkDUUDFmDH3iyhsiNG5iVo1Qp6NoVLl7MM3dxfpA1FAxZgx/4swbrrdy9C4MH\ng60teHvD7t0YMdUOsoaCIWvwA3/WEGHdkxkzMKOPqyssX67l3HOyhoIha/ADr9ZgxMVhbo4GDaBc\nOZg0CXsuBUHWUDBkDX7g2BqM9HTYvx93WjE3h169cKcVjUvsyRoKhqzBD3xbg6FSwfXrMGoUDsp6\ne8Mff0BqqnToDcgaCoaswQ/cW0Pk2TP4+WfcosnFBebNy9kwIRdkDQVD1uAHmViDkZaGm9e7u2Nu\njjFjxA0TckHWUDBkDX6QjzUYrLcSHAxt24KFBc7muHUr12wOsoaCIWvwg6ysIXL1KgwciAMrtWvD\nf/9BcrJUTtZQNGQNfpChNRgRETB1Ku604uAAy5bBkydiMVlDwZA1+EGe1mCwJsZvv0HjxrjEfvx4\nbICoVGQNBUPW4AfZWoORlQXHjkH//thb6d0bjhzxfXHLpRMIBUHW4Ac5W4OhVsPNm/D557hStmnT\n8VWrWmXXIh0lFARZgx9kbg0GE8ezZ7B4MVSp8sTEZKIgWJI1lAhZgx/kbw0RlYrVATVqZAnCSmaN\ntDSpnFAKZA1+UIo1spnn63tcEDKYNVq1wp6LrpkECQ4ha/CDoqzh6+tbTRA2MGuUKwdvvQW7dkFC\ngnSMkDlkDX5QmjVYFdbMGjNngocHTj9ftAhnc6jV0hmEbCFr8IMCrcHAvskff0DLllC5MowbB6Gh\nueaeE7KDrMEPCrUGIz0djh6Fvn3ByQlzc5w6ReKQNWQNflCuNRisxXHzJi6QdXDAnVa2bZPKCRlC\n1uAHRVuDoVbD8+cwfz7Y26M75szBNgghQ8ga/KB0a+Swdy8m9bGwgEGD8kvqQ/AMWYMfSow1GDdu\nQLNmYGODiUjPn4eMDKmckANkDX4oSdZgREbCkCEYH23enP1Ouu0LSRQLZA1+MLY1xo8fv9pgeHt7\ni7VIteZJTAx8+y3UqAFeXvDjjxAdLZUTfJNjDVdX114Go3HjxmItZA0NGNsaxkGqNT/i42HDBmxu\nVKqEuTnu35fKCY7JsYZxIGtooERag5Gairk5unfHfSG7dYOgIKmc4BWyBj8Y2xrz5s0LMhjt27cX\na5Fq1YxKBffuwejRuEVT/frw55/sgykdIvgjxxpeXl4fG4y2bduKtZA1NGBsaxRzNPRNEhJgxQqw\nssIspHPmQFKSVE5wBkVD+aHEW0OEfUSqVsXt3fz9abUbn5A1+IGskQ3TxMWL0L49lCkDffpASAj1\nVniDrMEPZI1XuHULRo7EiectWgD7PSkhGE+QNfiBrPE6rHsyZw4m5nB1hSVLaDYHP5A1+IGs8Qbx\n8bBxIzRsiHPPx43DHe0JDiBr8ANZIy8yM+HECZzHUbo09OiBsdKsLOkQUUyQNfiBrJE/Dx/C5Mm4\nhX3jxrBpE4U5iheyBj+QNTTy/Dn88gtu0VSpEm65Qqvdig+yBj+QNQqC9VZ27ABPT7C0hAkTcPEb\nURyQNfiBrKEdQUHQsSNOIe3RA/N00GwOo0PW4AeyhtaEhsKwYbiFfZ06uNMK9VaMC1mDH8gahSEq\nCnNzVKkC1aphbo7wcKmcMDxkDX4gaxSS9HT46y/MJOjkBJ9+Cteu0YYJxoGswQ9kjcKjVsPx49C/\nP6Yv7tEDgoMpzGEEyBr8QNbQCda+uHMHh1Ts7aFePVy0QuIwMGQNfiBr6AprcSQk4E4rFSrgZtQ/\n/SSVE4aBrMEPZI0is2kTVK8OJibg5wexsZSbw0CQNfiBrKEPTp6E1q1xNkenTrjTCm3vZgDIGvxA\n1tATDx/C0KE497xpU9i+HaeiE3qFrMEPZA39kZAA330HNWvi9PMFCyAignoreoSswQ9kDb2SnIy5\nOVq2xNzFY8bA3bskDn1B1uAHsoa+SU3FRSu9euGgbOfOcOGCVE4UDbIGP5A1DEBWFjx4gClIy5bF\nDktAgFROFAGyBj+QNQxGRgZ8/z2ury9TBubOpS3siwhZgx/IGgZm927M6MPE4eeHq91o0YqukDX4\ngaxheMSdVuzscKeV06cpk6BukDX4gaxheNRq3FB25EhsdLRuDdu20b6QOkDW4AeyhrGIiMAwR40a\nUKsW/PADTQMrLGQNfjC2Nd57771PDIaHh4dYi1Qrb8TF4aKVJk1wwZufH46zEFqTYw1HR0cmDgPh\n5uYm1kLW0ICRHrDAwEDxZhgHqVYOSUuDU6dwuYq4aOX4camcKAhmDRMTE+kGGx6yhgaM3dYwDlKt\nfKJSwdOnGOYwM4O6dbH1Qbk5tCCnrWEcyBoaMLY1duzYkWUw+vfvL9Yi1cozzB3Ll0OpUphJcMEC\nSEmRyol8yLFG48aNZxiMXr16ibWQNTRgbGuU3Gjom7AmBrsaXl5gawsTJ+KqWZrNkT8UDeUHskax\nkpUFwcHw3nsoDl9fOHuWxJEfZA1+IGtwwNWrOKTi4AAtWrArhevfiDcga/ADWYMPwsNxNke1alC1\nKs7miIqSyokXkDX4gazBDQkJmASsTh3cMMHfH65fl8qJbMga/EDW4ImsLLh0Cbp1A2tr6N4d83RQ\nmOMFZA1+IGsUF0cnuLyg2Yc/Hwh9OfQaFgaffQalS+NOKzt2aF5in5l2wF96FxeXVsPXnriv1EzH\nZA1+IGvoH7VapZJmkOSFKjsp4J2l3tm/qompqZlLpzk7rySLPyySlIT7yNrb404rv/2mIT6akbpz\ngJmZmalp9qzJFlO3hih1fQtZgx/IGnon6eLWGT7O4i+SF52/vhqeKFmjQq0BK/NJEciaGJs24eRR\n1uiYOBHjo/mmIE2/f2JVf1yCQ9YoKmQNbSBr6J3UO0fXTvygo0hjF3P2+5hZ2rg1bCMVTVn/4FlK\nwdYQOXQIl6tYWuKGsmfP5tNbIWvoDbKGNpA1tCTt8fkDf+08EZFSuER+ByfYsd/HpupbU3ZHSEUi\nWlqDceMGjBiBKUgbN8bcHAkJUvlLyBp6g6yhDbkfsKQ7R1csmj116qZQlfr+v0uniizdHPIwnh2N\nPfenWDB70YqjdwqRWoZPa4SdWDuX/a1Tp+67K5UApNw5snHh16xs6fHoV3sEMf/M7u1Rveng8ZP+\nb9qOe1JhwRTKGnEhm/7v/6Z+O2//3fgnxzYvxN+Msf5o3MMn8MMPmfZWag+Pu6NH/7Fuz+3oVxOC\nkTX0BllDG3I/YJH/zm3txT7o7UZMH9Chrr14BQV7txaD/SYPG9a3eVWxwKKsY9tP5h3TWhx8WuPO\nhhFujqXY+S0XXZWKkq7/6vdORQtBcB9+OP5Va6SfWvq/Wk745iamNTr8b9iU7/Y+lg5polDWeLD2\nfTNTExvbbkPGdm7oWhYrY1Rp2HPSlzP69R1uY3FaECIFYY1zrRnfBTyOzRktIWvoDbKGNuRnDZuy\nZYV2UwNOHN65cEyniuwqWllZm5l1nh544kTwlqkdWYFF2Sbjlh2Lln6uAPi0RvrN9T3cHE0EwaHe\nnCvZJQmXt3zczsVMELzGBia/HnxMjrx98dzOKW0dsmsws7Fza9Cy26Ql+x6+NviRGx2sYWJi41Sz\n9ieL95zYv9LPp44N/rxNWRPTEctOxGxZo2rh9px9ph3rHD98IkOazUHW0BtkDW3IzxpC06+Px6Vk\ngTrrwdHffOvjdew0LeB+bBaAOuburqFerKByj0l/3MqvtcEuOuuEv9gnmdO4hurByv7u5qaCjb3H\nonPs34khf37R2tmUSeOL/Q/zGrHISomLjHgSHrJlgifWY2ppU86xou+vIQ/zmyWhgzVKlavw8eor\niWkqUGWcWTGoDjpb+GhjRCKrIyvh/h/TTjkK8YJJgpuH+tCh7J8ja+gNsoY25GuNlotCxRLW+R/Y\nBK9jj3lHYrKnIsU9/tf/LVZQsdvEdaFvxuYYCQnQvz+Ym2Oqu1mzICwscMsWMQ0Tb9HQR38OLG1h\nKliXb/ndcVXCjTWfda3AZFBv7OFwjOPkhzorPSUl5dbBJX3Rp16fb7/GBJsnOljD0q6y/9YwseTS\nmqH1KuNf5LdPLEi+snNOj6rCdMEm1swSx1aWLYOMZLKGviBraINhrJGZCceOweDBmFzX1pa9zjVu\n/C5rnAjCvh07pHMMgA7WgCfbetpZsA6YZ/NpQTeDZgyoKwilvCdujkjIM79WSuSt0GtXr+yd3SW7\nHvOyDlVq1Bq27lJYfiMrhrDGuxhc8lzx4RfpNTxRzWP97m/51tedFZI1igpZQxsMY40cbt2Cb7+F\ntm1VVarECcJeQbg/dSqEhOQ1fKgHdLEGRO4aXoP9iF2Nhn6z5vZjHQ/rxlMDLie+0XZIeHzx2L+L\n+jvaZtdgbutYp03XD2etOhSmMQuX4awxYcuV5KAT4OMDtmUja1WaUFGwJGsUGbKGNhjYGgy1GiIi\nbs6c+bsgXBSEFNaobtoUmDt27YJHj6Rz9IRO1gC4/gMGKcqWdfL0dBWEci3H7LoW9YY0Uk8uGVDL\nEd/cxLRu7zET5y7574l0SBOGtQb7LR88gFF+Kke7M6aCr1B/3taTZI2iQNbQBsNbI5uAgAB7QfAR\nhLN9+0KHDmBjA+7u8MEHsHQp5qTR0x6oOloD7n/bWPw5Rjmfz1aHxrzZPcmer+H59phZcxYuOqjN\nmKuIwa3BiI5IneYXayWECuVOTpqeHK3luJbMIGvwg/GsgW8hCH9v3oyaCAiAoUOhYkVMYNWyJa6z\nOHIkZ8BFZ3S1Blxa2Fb8QcGhxZd/no7LI7SZ/vTGiX2HLz5LK1w+cWNYA9LDg1atrCqcFkxSK1ZU\njRwJT7RpBskMsgY/5H7AMhOe3rx2MSQkJDRSWmeZkRRz/wYrCLnzNDEze35AVkbCo+us4PKdsJhU\n7fI/5B55VakgMhLOnIHZs8HTE9NJuLlhXoktWyAxMfsndEFna2TE3Me/kHHldsRzLf8mrUh4jBfz\nwpXr4c9fb0/lZY30Z/fOnw85f/Hyozjp5JRnD65fxt8re2ouQ5XyPOL2FVZw7XFsikoaHMaR14Ee\nQnOhZlB5L7WtLbRpA9euiccUA1mDHwr9gOlG3vM11GrcVYh9Ma5fjzuSlSqF+hA3NIx4/ZtZO3S2\nRjGQlzV0RZqvYSo0n718f8KgQXglq1XD3BwKgqzBD8VqjVzs34+zPMqUAQsLnOgxdiwmtkpJ0T6f\nlZysce+X5uLvyqjS8dtc+TW0JiN1x/vSuwiCactp285jo4S14EqXxvQcCxdiqo58l9jLCbIGP/Bk\nDRHWtJ44ERo2lHLS9O0LO3fiSIEW+wzJyRpw4v8avqCT38rDt3VLTJ6Zfniy9C4NG3adsOnMi1mq\ngYHY9WPXcNw43NE+K49Qjbwga/ADf9ZgsO/GR49gyRLo3Rtq1sSdDd9+G3NbHT+uMTmNvKxhYFgD\n7eRJ6NIF483vvw/BwUUPNhcvZA1+4NIaOTx7hg2NTz+F1q2x58K+PFm3ZdMmuHOHfYikc16BrPEa\nTByhoTB6NFSqhNrdskXW4iBr8APf1hBhfZOzZ3FmR58+uF2IszOOtsybh9+lr0PWyIOwMLxWbm7o\n3O++M9CsXCNA1uAHOVhDhPXM796FPXuwo+7ujg3vBg1w0sfevTmDtWSNvHn+HNcf162LO618/DEG\niWQIWYMf5GMNEeaO2FhMird4MW44ZGGBTY82bTCRd1QUWSNfWN/kyhXsp1ha4tzcEyekcvlA1uAH\nY1vDysqqjF5g72Nq2lEQ9jNHmJhAqVJRNjbzzc2rCIIJWSNP1Grs6w0bBqamKNyAAHkNrORYw9TU\ntJTBMDfH7NAMsoYGjPSABQYGmpiIGTb0jJkgNBCEFYIQJgipgpAgCBuZNU6dgvh4fS1vURRpaTga\nxboqlStjqIh1XmQym4NZw0AfoTwha2jA2G0NT0/PZoZhYLNm8+ztjwtCBLNGqVK4IQDrtoSGoj60\nnidWIkhNxfGUBg3QHV9+ibM55CCOnLaGk5OTdMsNgIcHZjdikDU0YGxrFDWuoRFfX18nQfiIWWPQ\nINzu0NYWZ4tNn46zTsPD5fKlagwyMzFFY7duOI/O1xdOn+ZfrDnW+OSTT6QiA7Bu3TqxFrKGBpRm\nDbEWbIcfOoS+YC0Oe3sccxk6FFasgMuXFTBLUm+wq+Hvj+Jo1gxnwWgx+7YYIWvwg0KtIcLcce0a\nrFmDIUBnZ7Czg/btYcoUOHhQvtMW9Axrgi1YgKt+3Nzg++9x6i2vkDX4QdHWEGGt8SdPcDY6a3qw\nDkvp0uDlBQMGwB9/QEyMdE5JJikJ9u3DURUHBxg1Cm7elMo5g6zBDyXAGjkkJsLDh/Dnn5hrs0wZ\nfEgaNYL58+HpU+mEEotKhY2yLl1Qqey/Z85wGOYga/BDSbKGiDo7qcfJk9KqfDMznCrGPoiKS2NT\naCIiYMwYvBqenvDvvy8DQKyxtns3zJ1bvCnCyBr8UPKs8Sq3b2OYo0oV3HvZ2hreew8Xy0VGolZK\n5oDL8+cY3ahcGUPIa9Zg54WRkICb2jg64rT04rssZA1+KNnWEImJgZUr4d13wdUVBxS8vWHRIjh/\nnufQoAFJT4e1a3E2B+utTJqEi1aYKfbsARcXmDChGCNBZA1+IGu8gH2jiqvymzXDiR61a+Oo5I4d\nuCq/BM4xPXgQunbF7lufPhAUhCHSfv3wmly4UFzNDbIGP5A1Xic5GWejs7ZG377YJndwwMdm/nyc\nB8UOlShCQ9Gb5cujRtevxxEo9v8rVhRXkg6yBj+QNfJCpcImxvbtmIuQfcGWLQvNm2N6m4AAqatf\nQmD9kcWLcSpHzZrQsycGgDp0KK5OClmDH8gaGmFPyNmz8NNPmEyMuYM9P++9hw9SeLh0glK5fRt3\nqGH9kefPMQVp06YYLba0xGBHcLB0jnEha/ADWaMgWDc+NRUHVtjDw/r27LFh+mDfvV98gSnUFUlK\nCg5LV6iAqQPd3VEZTZqgNdiFZa/x46XTNBB/bc2kDxq6vcDzre5Lz0mHdIWswQ9kjULCei5+fjjU\nwmphDxLziPwT+eYBu03sT2vZEnOXiC9RGexla4sazZ+ku0HT+roLgslL2C0pU63z1N1F2UuSrMEP\nZA2dePYMQ6TsG9jeHszN4Z13YONGzNCZnKy0iR6ZmSjKPXuwX+bvj3GNGjVwsCl/kh+dXTiqn98P\nux5K4eOHP/pYCoJ1vU5fHIkUS3SBrMEPZI0iEBuLiSpYY75WLey5sMb87Nm44CU8HB82BcP+8AJI\njbx1OfiQxPLhtdhNcX+7/7Yb0mEdIGvwA1mjyLD2xbFjmN6mXTucVensDEOG4NK4S5dwjmnJIzPh\n6bl/fxn1biNH8Wa8gKyhGMga+uPyZfj9d/joI/DwwO3yWbfl66/hv/+Kst+1DEl7dHLth7XsBKF8\nk54jpsz6hjE6exd8soZiIGvoFZUKuyf//AMzZ+KqfFtbqF8fV+Vv3KjbftfyIzP21Lpxddg9qNFj\n6cFbadlLZ89914wVkDUUA1nDAKjVmKz0+nXsp3TpggMQVargrgLffIORRe5z7RWJ9OigFSPc2T0o\n22HevmsYDz2zuIFrGVZA1lAMZA1DkpEBcXGYroJ90O3sMGLq4oK5CC9eVNpQSw5qVfjZzUObsptQ\nqqy9U2VnZ2cHG/GmkDUUA1nDWISF4XrzGjVwpJa1Pjp0wPEXphUlNj2eX9w28l03S4mRO0LmNbW0\nrNV+QECodIIOkDX4gaxhXKKjcVW+jw9Ou7SywqjHokVw9SpO3FZ2z6XIkDX4gaxRHLAmxr592FVp\n1Ah7Lu7u8PnnOJPq/n1KoZ4fZA1+IGsUH0wQFy9i7qzu3XGvfEdHnDC2fDlmJyxpq/K1gKzBD2SN\n4iYzE5sYmzfjfG3WYWHdlmbNMIlWYGBJGazVDrIGP5A1uCEqClsZixfjHFNbW4yb9ukDy5ahUyjk\nQdbgCbIGZ6Smwt27mBP8gw8wkxjrtrz1Fk5Xv3JFOqGkQtbgB7IGl7DGRVISmoL5gonD0hKDpp07\n44YDyl4Xlz9kDX4wtjU2b96cYDB69+4t1iLVqgxiYzFbJ+uwWFmhPho2xNUurDujvKQeGsmxxtCh\nQ6X7bQB+/fVXsRayhgaMbQ3jINWqJNRq3I6EdVtcXTEbkJcXfPUVDsEwfZSM1keONYwDWUMDRnrA\nAgMDpbthFKRalUdaGqYOmzwZV7WwnouTE076+OsvzCeu9MFaZg0xK5hxIGtowNhtjR49eow3GDVr\n1hRrkWpVKioV3LgBS5bAwIGYwbR0acyBPGcOrsqPi1PqCpectkbdunWl+20AOnXqJNZC1tCAsa1B\n0VB9EhmJoy1TpkCrVpjKtH59GDkSd1pU4n7XFA3lB7KG/ElMxADHypXQuzd2W6pUwYRA334LISHS\nCYqArMEPZA2lkJaGCYHYZ93PD3Mg29ri1vDDh+O2JhpTissFsgY/kDWUhVqN+oiOhnnzcLTF3Bx3\nb+nYEcdfUlKkc+QJWYMfyBrKJTkZtm7FVflMHEwfNWviqvyICNSHDKeokzX4gayhdFj3hHVShg3D\n7Rfs7HCW+tix2JEJC5NXCnWyBj+QNUoM58/jqnzWWxFX5ffpA6tWYWFCgnQC35A1CiIt8nbIga0v\nOBSq6z7mKU+und4vvcvWbYdvvzkRiKxRwmBNjPXrYdQoqFcPg6atWuHA7Z49+Q7WsvNXr4abN6V/\nFh8KtYYqMerGnpXzX7JL12WKGWF75n5UQ/ztGc3n3pMOFJawv2cN9JTeRTD1mHFZKn8JWaPkoVbj\n2hb2VMybB506gY0Nzk8fMABX5TM75Ap5sN6NkxOMGYP6KFYUaY3MlNidczp5lhPrzKbmO/7+G25J\nx3OIC17xpX9+jB3/zZ47kHRvy/S+zuwdaneZMmfhsm3n46WfLSxJ988c3LBs7oi2rtbmgqnZqCNS\n+UvIGiWYlBScir5tG0Y9ypdHO7Cmx6RJmFQ9Z2nco0fQsyf2aBYuLN5J64q0RkZi5Nov2r4zYdne\nbBaPbFC+NKu8Wo81l6QzJB6v6lVR/MXywKJ03VlBL63RafqFR7oa4yVPt/p721mSNYg8ycrCza4v\nX4apUzFiam0N1aqxSyltAc2aHkePQp06UL065jotvsEXRVpDrcqKfxYWHieFpVNidvm74EaXlep/\n+7o2MuMe37qeTfCulQOb4G/o1nvKrmMXsehG6N3oZLKGjpA1igTTR3Q0hkgbNoRSpcDCAnsuy5dj\nyIMV2tlB+/Zw+7Z0stEpGdHQx7/3xd0t7av23x4uFeUi+tr+sW3wN/Qc8tO1p6/M3yNr6AZZQz9k\nZmKzomtXHKa1ssIxFz8/3MDFzAzGj8dNGDSSdDdoWl93QWg+ef2ho8t8bSzN8JbYu3f/4d/IyMjr\n22a2fNGP77Tw7PNUbXOyy8UaCWGXZnUxZ+/QdPiCkCdS0yzlWdDY2oJgWqGT/69X8x+zykj6d4Kr\nE/tZB/cP/84naWyhrJEWGbr0Yy9BqDt8XuB/60a5OWH/Ryhdrsm03U+jom7t/alnE6yO0XRWUGzy\nq/eCrEHoxtWrGOZo0ABDHkwZ7MKyBsjq1Zr7KS+sUdnV1daheu3mLVo2r++C+6+VK+dUqZJbJY+G\n3q1a1a1mamJibuMw4MfzWg4QysUaGbH31o1vZsneot7gjacfiw9ixIGJNQTB3LnZhDXn8vh70xMf\n37oUHBy88tMm9tZYe6Mxu6OkY7nRyRqOzs4OFWpUb9ysRavGHrh9prW1XbVqHo5V6zZp1aq+m1Up\nNHvHWade2cecrEEUlqQk3Kf23DnYvx9+/BHTebBGB7uw7FWxIgQFSaflxQtrCLbVm41dcy4tU510\na2vfanhfyrvU9l96AD/SN9a1cmZfyFaezaad1G6VjGx6KJnPz236ojE+mjXHrAmOyWBFiTtHezBp\nuLQctOFyHi2NjAfHpn9QT6yXtcqa9By4+bp06E10soZQxqXexz8djErMhMgDg/HmCGUruH00Z3Po\nM4A723s3cDRhaqnq/9/LeDdZgygsGzZAt244pOLmhmvwTUxwckeNGtCiBc4TW7xYw25POdaoNXz5\n7WiM82UkxfzcF+9Lg36TDz8Qz3q4xId9H5dya/TJPu2W9csnrpH19MK2kS3s2JvUHPHr7eh0iDs4\npCr7W53eHrbiRl7DUGn3jkztzzowglOTnuMmLQlmT3L+6GYNj/4zT9yX6t4wCH+8erv/BUqzcMLX\nvu9qaiKUd+6z9eXwOlmDKCzr1+OWTj16wIQJMGMGZirdsgXbHadPYw7kiAiyhgYyoy8vH9MWgzdV\nBwfcjFKdnO4kCJYVvUatuZp3uyr81DcfebPT203bFZlUwCgVWUPPkDX0Rnw87sNy9y4Oyia+0tvV\nArIGZMUG/z7B24G9jcPIjTeCZ3oKglnl2r4bb+WTIPqFNbp/fyi6oJXJZA09Q9bgAbIGgDo9dNeo\nzjgt22bwyLEOpQRz67cGrX6QX/ssKy0uKuzu3bsRcSlZBeVvJGvoGbIGD5A1srn/17heruyNslMk\nm9uUH7bxkXTkDRJu/PN5dzdTU9N6Y/94Eo/hUw2QNfQMWYMHyBoitwO+aOWBEzcYZSr1C3gilb/J\nkzMbhzbHMy16zb//rIAuCllDz5A1eCD1yeXfpw/w8fH5aP7OsOf4zZmZmrB9OivwGT5j+QXJEU8D\nJrzr49NxwIgFp2PEkgKQnTXgwX9TR3+Af7aPT48v/85v/gUj+eGZpV++z04buvjAs6R8w8wiz++f\n+elTfM9B3297EPNKoCQva2TEPgqcN5id/L+Za65GSIo5OAd//MPxs4Ok1k/0vlkftPfx6d5v+pFo\nsYRB1iDkj/ysYWTyskYRIGsQ8oesUQA51qje1m/CVzN/C4qVDhSW+NDD236eOdG3qbOVGVmDkDNk\njQLIDN87f2hONh29ZeXxmn1VKn8JWYOQB2SNgsiIC78dcuwFFx6/EiktFGkxD0PPSu9yLOhSOAa0\nX4esQcgDsgY/kDUIeUDW4AeyBiEPyBr8QNYg5AFZgx+MbY0xY8asMBhNmmQnVCRrKJEca7Rp00a6\n3wZg6NChYi1kDQ0Y2xrGQaqVUBA51jAOZA0NkDUIeUDW4AdjW2PBggWnDMY777wj1iLVSiiIHGv0\n7t1but8GYObMmWItZA0NGNsaFA0ldIOiofxA1iDkAVmDH8gahDwga/ADWYOQB2QNfiBrEPKArMEP\nZA1CHpA1+IGsQcgDsgY/kDUIeUDW4AeyBiEPyBr8QNYg5AFZgx/IGoQ8IGvwA1mDkAdkDX4gaxDy\ngKzBD2QNQh6QNfiBrEHIA7IGP5A1CHlA1uAHsgYhD8ga/EDWIOQBWYMfyBqEPCBr8ANZg5AHZA1+\nIGsQ8oCswQ9kDUIekDX4gaxByAOyBj+QNQh5QNbgB7IGIQ/IGvxA1iDkAVmDH8gahDwga/ADWYOQ\nB2QNfiBrEPKArMEPxrZGhw4dhhoMNzc3sRapVkJB5FjD09NTut8GoE2bNmItZA0NGOkBCwwMFG+G\ncZBqJRQEs4aJiYl0gw0PWUMDxm5rGAepVkJB5LQ1jANZQwPGtgbFNQjdoLgGP5A1CHlA1uAHsgYh\nD8ga/EDWIOQBWYMfyBqEPCBr8ANZg5AHZA1+IGsQ8oCswQ9kDUIekDX4QasHLObkqj7eFdilbDLz\nqFRUSMgaJZms1PjAifXZfanyzojtl55LpYWErMEPZA3C4JA1FAZZgygMiYmQni79v9aQNRQGWYPQ\nmthYWLQIfv4Zrl2TSrSDrKEwCm0N1fWtk0W+XrLr3KM06ZQCIGsogchI6NMHbG3hvfdg5Ur8p3a8\nZo0DR37/aY74CZq1+rT2CiFr8EPhrFG+Trt+rd3FyypYOXh6f7Im6HaSdJYmyBpKQKWCixfhm2/A\nyQkqVoQPPoC9eyE1VTqaPznWKF3BvWXzxpXKW4u3ybJyy0+mBt6XzioAsgY/FM4aDNN+P587d2rP\n+q87VWX/smk2duXNZwV3dMkayiEhAc6cgcGDwdoa3NzA3x9CQ0Gtlo7mRY41kIa+P20+eO7c7i+a\nWLBPk33Nd34MfiadpxGyBj8U0hr9l8UkZbASVeSVX0a3ZAVmdT4OuPY0SzzvVb7/Hnr0yHk98fb+\nmylDEJ42a/ZquX5fZ52dxVpyldNL/y8fH6hSBdiltrCAatVg+XINUdKX1nirx/y9oRlZTDGq1B0j\nWIGJrXufbw7ESidqgqzBD4WzxivR0GdBv41rhJe3w6KT9/KIbnz4IX4XvXhlWVomCwJ7sf95tVy/\nrzQzM7GWXOX0MsjLzAytIYrDxQUOHZJu/RvkEw3dPwg/PxV9Plx1UyrRBFmDHwxmjTt34OzZnNfh\nH35oKgjsdWzRolfL9fv6qkMHsZZc5fTS84sJYulSaNAAfcE6KRMmwL17GjopZA2FUThrVJ+0TypK\nD9+7cAjGRct0W372QYGBDYprKITUVAgJgWnToHJlfL3/PvzzD6QVMJKWYw37t4dsOBstlUaubceK\nzJ07jvxTm4AoWYMfChnXaPzh4n/ZLc6Iub7r87YerKB8u0mH7sSqpBPzhayhBOLjYcUK8PYGKyvo\n2hV+/x0iIqRDGnkZ13Cu32/OtnvRKQBh//m3ZQWlnLyGrziXLJ2oCbIGPxTKGpWrVTM3qddr/Hj/\nwX1aVWGXtvxbH//8z9OkPIKhuSBrKIEHDzAI2rw5LF4M169LhVrwwho25crZ23rV7zVw5Pjx/eub\nmQpmVu6dJx94oI00yBocUShrdJi5bdMvw2uJl1Wo2njw3B13oxILbGgwyBpKICUFTp6ECxcgA8fR\ntOeFNaq987+vly0YVrdaGfE2le8398jFcC0nCpI1+EGrBywrOfbBneuXLz+IzchKi75zWeTm/agE\nbZckkDVKNGpV/JNbly+HPox4npIUfffmNfETdCMiUTpBC8ga/GCkB4ysQRQRsgY/kDUIeUDW4Aey\nBiEPyBr8QNYg5AFZgx/IGoQ8IGvwA1mDkAdkDX4gaxDygKzBD2QNQh6QNfjB2NYwNzcvZTBMTU3F\nWqRaCQWRYw12l6X7bQDY51OshayhASM9YHv27ClTRppHbGisra2lWgkFwaxhb28v3WMDY2lpeezY\nMali4g2MZI1Hjx5Nnjy5tVGYM2eOVCuhINRq9dKlS6V7bGDGjh3LPrFSxcQbUGOeIIjCQdYgCKJw\nkDUIgigcZA2CIAoHWYMgiMJB1iAIojAA/D9gc1x0eGntKgAAAABJRU5ErkJggg==\n", "text/plain": [""]}, "execution_count": 3, "metadata": {}, "output_type": "execute_result"}], "source": ["from pyquickhelper.helpgen import NbImage\n", "NbImage(\"images/dicho.png\")"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Version it\u00e9rative"]}, {"cell_type": "code", "execution_count": 3, "metadata": {"collapsed": true}, "outputs": [], "source": ["def recherche_dichotomique(element, liste_triee):\n", " a = 0\n", " b = len(liste_triee)-1\n", " m = (a+b)//2\n", " while a < b :\n", " if liste_triee[m] == element:\n", " return m\n", " elif liste_triee[m] > element:\n", " b = m-1\n", " else :\n", " a = m+1\n", " m = (a+b)//2\n", " return a"]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [{"data": {"text/plain": ["2"]}, "execution_count": 5, "metadata": {}, "output_type": "execute_result"}], "source": ["li = [0, 4, 5, 19, 100, 200, 450, 999]\n", "recherche_dichotomique(5, li)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Version r\u00e9cursive"]}, {"cell_type": "code", "execution_count": 5, "metadata": {"collapsed": true}, "outputs": [], "source": ["def recherche_dichotomique_recursive( element, liste_triee, a = 0, b = -1 ):\n", " if a == b : \n", " return a\n", " if b == -1 : \n", " b = len(liste_triee)-1\n", " m = (a+b)//2\n", " if liste_triee[m] == element:\n", " return m\n", " elif liste_triee[m] > element:\n", " return recherche_dichotomique_recursive(element, liste_triee, a, m-1)\n", " else :\n", " return recherche_dichotomique_recursive(element, liste_triee, m+1, b)"]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"data": {"text/plain": ["2"]}, "execution_count": 7, "metadata": {}, "output_type": "execute_result"}], "source": ["recherche_dichotomique(5, li)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Version r\u00e9cursive 2\n", "\n", "L'ajout des parametr\u00e8s ``a`` et ``b`` peut para\u00eetre un peu lourd. Voici une troisi\u00e8me impl\u00e9mentation en Python (toujours r\u00e9cursive) :"]}, {"cell_type": "code", "execution_count": 7, "metadata": {"collapsed": true}, "outputs": [], "source": ["def recherche_dichotomique_recursive2(element, liste_triee):\n", " if len(liste_triee)==1 :\n", " return 0\n", " m = len(liste_triee)//2\n", " if liste_triee[m] == element:\n", " return m\n", " elif liste_triee[m] > element:\n", " return recherche_dichotomique_recursive2(element, liste_triee[:m])\n", " else :\n", " return m + recherche_dichotomique_recursive2(element, liste_triee[m:])"]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [{"data": {"text/plain": ["2"]}, "execution_count": 9, "metadata": {}, "output_type": "execute_result"}], "source": ["recherche_dichotomique(5, li)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Il ne faut pas oublier ``m +`` sinon le r\u00e9sultat peut \u00eatre d\u00e9cal\u00e9 dans certains cas. Ensuite, cette version sera un peu moins rapide du fait de la recopie d'une partie de la liste."]}, {"cell_type": "code", "execution_count": 9, "metadata": {"collapsed": true}, "outputs": [], "source": []}], "metadata": {"kernelspec": {"display_name": "Python 3", "language": "python", "name": "python3"}, "language_info": {"codemirror_mode": {"name": "ipython", "version": 3}, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.1"}}, "nbformat": 4, "nbformat_minor": 2}