5-dichotomie
important
Recherche dichotomique itérative
On considère dans cet exercice des tableaux non vides contenant des nombres entiers, tous distincts, triés dans l'ordre croissant.
On cherche à déterminer l'indice d'une valeur cible dans ce tableau à l'aide d'une recherche dichotomique dans sa version itérative.
Écrire la fonction indice qui prend en paramètres le tableau de nombres tableau et la valeur cherchée cible .
Si la cible est dans le tableau, la fonction renverra son indice. Dans le cas contraire, la fonction renverra None.
Attention
Les tableaux des tests secrets peuvent être très grands. Une recherche linéaire naïve prendrait trop de temps lors de l'exécution.
Les tests secrets limitent le nombre de lectures dans le tableau à 100. Si votre code accède à plus de 100 valeurs dans le tableau, une erreur sera levée.
Exemples
Python Console Session >>> tableau = [ 23 , 28 , 29 , 35 , 37 ]
>>> indice ( tableau , 23 )
0
>>> indice ( tableau , 29 )
2
>>> indice ( tableau , 37 )
4
>>> indice ( tableau , 10 )
None
>>> indice ( tableau , 100 )
None
Question
Compléter le script ci-dessous :
.128013]ik[vN8o-)yqxb.I+g=DmT4r*s97f,d :C5hwtcOl0p_PL3(a;ER/àeîèS612énu050F0%0M0X0c0P0A0G0N0P0X0A0A0t010M0c0R010406050A0:0v0v0X0y0l040*0i0P0:140i0/0G020X0v0R0Y0G0!0%1e0y0m0:0%0A050#1b1d1f1h190R04051M1F1P0#1M190F0c0f0|0~10120~0/0s0:0X0s0%0j0R0l0M0K1o0G0K0c0s0K0P1^0K0M17050@0o0P0%1Y0 11011@1_1{1_0M21231 0M0y1N1:0|1k0A0R0X0/120-01251!010D0_0%0/1s0%1 2n2p2u272x232A0v2C040a0G0T0y0i0R0i0A0c1n1p0=2l0y0y0%0N2X1F2E0/1N0#1:2-2h2j2i200F2G1#0c0/2z2U1 1V1X0}262`2|0/0i301 0R2$1N2+2-3d1a2o1p322v360y1e0P1 0X1?2$0D12030S0S0N370%1{350i0j0,3E170G0,1F0X3e3h183g2F3j273l3n3p3r0%3t013v3x3z3B2}3E0j2s040G0-3K3M2p3O2+2_013T0X3o1N3q0K3s3u3w3y0=3%363)0V3H0V3/2*3N193?3R123_3{053}3 3Z413$2{3(3F0x3H0x4a1G4c3P3i1Z3S0i3m3`3V3~3X403#434p453F0J3H0J4v3d4d3h3@4h4F4l3!423A4L3D3F0+3H0+4R4x4e4A4g4C3U3|3W3Y4Z4o3C3)0C3H0C4,3;4T3Q4/3^4;4E4?4G4^4n4K4{3F0h3H0h502,524z33554D4i4k4H4m4J4#5d0j0B3H0B5i3=4U4f5n4=4j4@4I4!444%3E0Q170,0Q5A5k4V565p5H5s5J4$3)0,0,5O3J0#3L4b514y5T5o4X5r4_5c4q3E3+0,3.5)3:2,1Q3b1F302:0F2j2^5D4!2 1W1N3a0%3c3N5+5~4!6e2F0c0F123w2+5!3V6l6n5t5K6q0G2K0%6t5Y5v5$2-5*4.5m0d170=0D6g6j5l2v0L3H6M5-5D0/0D172{1V0N0%6S6G2v16040W6$5C540/172e0%0X0:6,535m6)0E6M0G6T6.170N0c226#4w3;6 6`170k0H6M19765~3?6s016o3h3)3+5G7i5b5u5@2s6x2B6A4`7s1 5|0G7B6~6%3S6J0%0o1m6}782v0i170t7K7E120v0c175Q7f3O7X5-7p0S6p3F474?7#6B5@477u2L7w5?4M0j7)3/7C7D6-5m6/042x0/7Q7|7M7O826_3k0o172J6^6O276)6+7Z7R3^6:0X746?8c3@6)0k868d127N040j8s3@7T5O7d8o7#7%0j4s7*6m7j6u5Z4r2t6y7;7r7?8H7_7C7L276I040L1@238y6U7G7I0M8%548v020P0M0Y7P7X7{877F7 2{8o5D6)7c7X7e3f7h8J7k2p3)4O8I8Q6v4N8O7v8K7,7?998U7`7B8W4g177T1{0%6@8@9n018v8?3d8^8t018f8}70040=8*8,5m8v0r9J3k17809E79048r9u8i8v0#0#9N278A045{4S8D957$7l4(6r9+9h5L4)7/6z9g7x7?4)6E3,9l9m8i8Y0c6L9V838`72749!8u178/8;aa8j046;8n8ha6126)0e9R9O049q0c9sap8e170b909)ak6k9+8F4}9a9_7=5L4}9@9b8M0jaF9k9 8V8i7~9Qa58_ab049y3N9A4V9p0_at9t9z9v8v8xaW9B9$5(aA934U8E9-0j5faG7q9ca|9e7:aH8R5La}aQ7`9v8Y4#a4a,aT71738$a:3@9xa!3;a$8(ah8l23aja^aX9C17aoaB9B7~asaubz8paxaz4xbEa`973F5xa~8L5v5xaLb4b0bNb8aRba172$0M0:0y81bjbpbCa+bIbu1pbK0/5!5NbO9;b=b29^a aN5P7z3LaRbo54bb0`75b.bF04bH5,bJaDa{5#9/aM6C5$bSb|cib 9~c1a0alag9H7Jb)8-85cv7}a(9rb,bna-179Mcy2va=8Ccc6t8F5`cgbTb}7t8PcQ6C7n7AaScr8Yb!b$b(becZ0N170g1oc6b-6f0#6i5 6d616a1F0M64c`2?2.brc@0#621L6N3@2$0v0S0D0X0d0%0S0K7)1x1z1B1D0Gca5~1S3O303@0X0F0v1o2W0c1=2{0D8v1Ldrdtdv2X0j140M2f041x0N0K0%0ydN246Z1;0M0i7Tdj0G2W0.0y0X140f240H0G0$2l0/2A0(2h751T1O040q0P0G0A001*2W0G2Z0Pd~0P0s4C2W0K2Le1242$dRdQdOe10cdN0idVdX1C2G0cdj0p1Q7Yd30;1WdDdu0/dwdy6VdB1OexdFdxb;dIdK0U3qeddOefdS24e36YeidS0:0Gb+esd40U240N3`0N0:d{e200eT6!e1eWb+eXd#2W24dV1m3X0i0c0{dj0Pdj0{3y1d2z0@0c2$0A0p0G0q720G1=3a2S2U24054!3@1$1(1*1,1.1?1|2b1}2DcrbBa)bDc(bv9xaf9DbEbpct8+cH279LafaU8|fH548qaf9X9ZfL7S7U9%6Sc;3z04erdod40O0y0Ee12pf3dPf70/0{fofq0{2Zfh0sd$1I2X2lf50G230G0If.0~0Gf70Pg50=0{f6at0ygf0A0Mg40c7T0M0.0%fb0Ie$e(e*6~fm5Dfo1)1+1-0lft2a1|1~d5b*fAcC2,c29KcxfC9BfGc7fI7HcugRbkcFfO9PfQgUfS7afU179Yaf9$9(c:6i0G0R9sgl2o0ydAe~0G0%0n0N0.0=0y0|0?0Me_0^gceRgne^fb0Z1p3X0D0?f.2Vg4dk0=0:0ndZ0/6Zdkfl3zfn2pfpgCfs291`gHfxbv7~fJf#g=0?gxhwgzhygBfrgEhCfvgI9vfPc%g;f%d|1oglf~2p0F0Ag89sh40AdWeahv2ZhO1%hQgDgFhD2chFbA8)gXa#cE04cGgYbpaV3ff$0=3,g@1me10.2o10dPg43q0f3`h-gmgogreZd^0uf:h50|0 ff3igvg5eShseUe:eXgLg~1p1ma)0A2pglg90~0y1+b$ebg4e-0/h70yimhadlhMh?54gAfqh`hThEgJ9FeYfX9wgQi2bf9GgWfKi6cwi4fF178gg(cz8{hYcD9W17a/i~j5hIfR9S9Ujc8404g-i?g/hJf%f)d@1Miuf@hmix0{3a0.0Af6h,g?2R220)ea2|d|242TjAg?iye%f-iJ2P1/1;0/h,gfiYgh0{0/00h$jNf{h80_iChch7fb0w0ie{g|h+0G0*0ciW1=0Xime01eez0Re*0.ebj!dW0of90G0D0Pek0@iYf^jKjE0PjG24jAd$e00X0Rg`eW90d@dq5DdseyeAhg0n1s0RdKdCkwdEezdGeJ2M0Z0n1ykDd?dpewh@hzhR3y1pi.h}i:5m2I2z2B170TjT1=0I1oh/g50*1D2V1o6S6c6N5}1Nc=94cM7l0-3Gb@9`3Dl1cjcTcl3(l62t595Il43*l24a8i0s6)020s8;lmloln1vav9oi{9Ii?fEjm6W9%0p7WjifM170z0zg.fZ5P0-49919*k 97l17n3q7+lflSb`chla3*lc4Yl945lX9}9vlkaclrlp0Yl:6~jfaqi8a#cqfDi^j8cr0vlA0-lCg+04lHlJ5O0QlMm4i5i_l lKcKc7b:lg7^lU9:lW7@lYcUl!7.ld5Xmn7^5|l,lll/mA8;l?j4aqjelEaYmcl~hGg$j7gNgO2v0N6D03ifihjA2LiYiVe%2o72gpmg6fk~8K6pl18TmllZl)8Gmpl(l5m=5W5=b5lg8Tmxlj8vdzm(77m*96b;l19jm/mqm;4OckbPl!ndmtm{6vn8cnmyl.lqnplsl@aw6*ltcsi|mbg#j6nvfTlxg,m7f!8@mP27mR17mT0Fig261yf6mZkp0Xm$k4kcgiiVg9h/f5n37ga_cdlR0j9|7ommaIlg9?l8nfm;9?nim@n;nmn06X6Vn%d5mil1aPnan{o4m?n@m^aKn`oalgaPm crl-04l:ollrmDm)fyi0i}mdl|j0i?gTopmLnAnD8wnzmGoygSg*oBfWmH01jnlOcLm+l0b1l3n:l15fneb^oUl$5;o7oRlioi8v0h0p0B0h0h0x0+0J0+0C0x0V5#0J0h0%0r0V0Q4 oNi9c=1S60d26a7eeup60fet0?h90A04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)