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_4:L2-.Sw3/]+7bpPiNqIo1tl(9î ;=vTm6u8Rs*èCfrOgà e[hEcDé05a,nkydx)050.0W0y0)0s0z0N0D0!0z0)0N0N0F010y0s0q010406050N0K0I0I0)0S0-040i0w0z0K140w0+0D020)0I0q0E0D0M0W1e0S0u0K0W0N050l1b1d1f1h190q04051M1F1P0l1M190.0s0G0|0~10120~0+0U0K0)0U0W0g0q0-0y0Y1o0D0Y0s0U0Y0z1^0Y0y17050@0p0z0W1Y0 11011@1_1{1_0y21231 0y0S1N1:0|1k0N0q0)0+120f01251!010R0_0W0+1s0W1 2n2p2u272x232A0I2C040a0D0r0S0w0q0w0N0s1n1p0=2l0S0S0W0!2X1F2E0+1N0l1:2-2h2j2i200.2G1#0s0+2z2U1 1V1X0}262`2|0+0w301 0q2$1N2+2-3d1a2o1p322v360S1e0z1 0)1?2$0R12030b0b0!370W1{350w0g0x3E170D0x1F0)3e3h183g2F3j273l3n3p3r0W3t013v3x3z3B2}3E0g2s040D0f3K3M2p3O2+2_013T0)3o1N3q0Y3s3u3w3y0=3%363)0k3H0k3/2*3N193?3R123_3{053}3 3Z413$2{3(3F0c3H0c4a1G4c3P3i1Z3S0w3m3`3V3~3X403#434p453F0(3H0(4v3d4d3h3@4h4F4l3!423A4L3D3F0J3H0J4R4x4e4A4g4C3U3|3W3Y4Z4o3C3)0o3H0o4,3;4T3Q4/3^4;4E4?4G4^4n4K4{3F0L3H0L502,524z33554D4i4k4H4m4J4#5d0g0B3H0B5i3=4U4f5n4=4j4@4I4!444%3E0%170x0%5A5k4V565p5H5s5J4$3)0x0x5O3J0l3L4b514y5T5o4X5r4_5c4q3E3+0x3.5)3:2,1Q3b1F302:0.2j2^5D4!2 1W1N3a0W3c3N5+5~4!6e2F0s0.123w2+5!3V6l6n5t5K6q0D2K0W6t5Y5v5$2-5*4.5m0,170=0R6g6j5l2v0j3H6M5-5D0+0R172{1V0!0W6S6G2v16040A6$5C540+172e0W0)0K6,535m6)0*6M0D6T6.170!0s226#4w3;6 6`170:0d6M19765~3?6s016o3h3)3+5G7i5b5u5@2s6x2B6A4`7s1 5|0D7B6~6%3S6J0W0p1m6}782v0w170F7K7E120I0s175Q7f3O7X5-7p0b6p3F474?7#6B5@477u2L7w5?4M0g7)3/7C7D6-5m6/042x0+7Q7|7M7O826_3k0p172J6^6O276)6+7Z7R3^6:0)746?8c3@6)0:868d127N040g8s3@7T5O7d8o7#7%0g4s7*6m7j6u5Z4r2t6y7;7r7?8H7_7C7L276I040j1@238y6U7G7I0y8%548v020z0y0E7P7X7{877F7 2{8o5D6)7c7X7e3f7h8J7k2p3)4O8I8Q6v4N8O7v8K7,7?998U7`7B8W4g177T1{0W6@8@9n018v8?3d8^8t018f8}70040=8*8,5m8v0n9J3k17809E79048r9u8i8v0l0l9N278A045{4S8D957$7l4(6r9+9h5L4)7/6z9g7x7?4)6E3,9l9m8i8Y0s6L9V838`72749!8u178/8;aa8j046;8n8ha6126)0X9R9O049q0s9sap8e170m909)ak6k9+8F4}9a9_7=5L4}9@9b8M0gaF9k9 8V8i7~9Qa58_ab049y3N9A4V9p0_at9t9z9v8v8xaW9B9$5(aA934U8E9-0g5faG7q9ca|9e7:aH8R5La}aQ7`9v8Y4#a4a,aT71738$a:3@9xa!3;a$8(ah8l23aja^aX9C17aoaB9B7~asaubz8paxaz4xbEa`973F5xa~8L5v5xaLb4b0bNb8aRba172$0y0K0S81bjbpbCa+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(becZ0!170t1oc6b-6f0l6i5 6d616a1F0y64c`2?2.brc@0l621L6N3@2$0I0b0R0)0,0W0b0Y7)1x1z1B1D0Dca5~1S3O303@0)0.0I1o2W0s1=2{0R8v1Ldrdtdv2X0g140y2f041x0!0Y0W0SdN246Z1;0y0w7Tdj0D2W0$0S0)140G240d0D0V2l0+2A0C2h751T1O040v0z0D0N001*2W0D2Z0zd~0z0U4C2W0Y2Le1242$dRdQdOe10sdN0wdVdX1C2G0sdj0h1Q7Yd30;1WdDdu0+dwdy6VdB1OexdFdxb;dIdK0e3qeddOefdS24e36YeidS0K0Db+esd40e240!3`0!0Kd{e200eT6!e1eWb+eXd#2W24dV1m3X0w0s0{dj0zdj0{3y1d2z0@0s2$0N0h0D0v720D1=3a2S2U24054!3@1$1(1*1,1.1?1|2b1}2DcrbBa)bDc(bv9xaf9DbEbpct8+cH279LafaU8|fH548qaf9X9ZfL7S7U9%6Sc;3z04erdod40T0S0*e12pf3dPf70+0{fofq0{2Zfh0Ud$1I2X2lf50D230D0Qf.0~0Df70zg50=0{f6at0Sgf0N0yg40s7T0y0$0Wfb0Qe$e(e*6~fm5Dfo1)1+1-0-ft2a1|1~d5b*fAcC2,c29KcxfC9BfGc7fI7HcugRbkcFfO9PfQgUfS7afU179Yaf9$9(c:6i0D0q9sgl2o0SdAe~0D0W0/0!0$0=0S0|0?0ye_0^gceRgne^fb0Z1p3X0R0?f.2Vg4dk0=0K0/dZ0+6Zdkfl3zfn2pfpgCfs291`gHfxbv7~fJf#g=0?gxhwgzhygBfrgEhCfvgI9vfPc%g;f%d|1oglf~2p0.0Ng89sh40NdWeahv2ZhO1%hQgDgFhD2chFbA8)gXa#cE04cGgYbpaV3ff$0=3,g@1me10$2o10dPg43q0G3`h-gmgogreZd^0#f:h50|0 ff3igvg5eShseUe:eXgLg~1p1ma)0N2pglg90~0S1+b$ebg4e-0+h70SimhadlhMh?54gAfqh`hThEgJ9FeYfX9wgQi2bf9GgWfKi6cwi4fF178gg(cz8{hYcD9W17a/i~j5hIfR9S9Ujc8404g-i?g/hJf%f)d@1Miuf@hmix0{3a0$0Nf6h,g?2R220Pea2|d|242TjAg?iye%f-iJ2P1/1;0+h,gfiYgh0{0+00h$jNf{h80_iChch7fb0H0we{g|h+0D0i0siW1=0)ime01eez0qe*0$ebj!dW0pf90D0R0zek0@iYf^jKjE0zjG24jAd$e00)0qg`eW90d@dq5DdseyeAhg0/1s0qdKdCkwdEezdGeJ2M0Z0/1ykDd?dpewh@hzhR3y1pi.h}i:5m2I2z2B170rjT1=0Q1oh/g50i1D2V1o6S6c6N5}1Nc=94cM7l0f3Gb@9`3Dl1cjcTcl3(l62t595Il43*l24a8i0U6)020U8;lmloln1vav9oi{9Ii?fEjm6W9%0h7WjifM170O0Og.fZ5P0f49919*k 97l17n3q7+lflSb`chla3*lc4Yl945lX9}9vlkaclrlp0El:6~jfaqi8a#cqfDi^j8cr0IlA0flCg+04lHlJ5O0%lMm4i5i_l lKcKc7b:lg7^lU9:lW7@lYcUl!7.ld5Xmn7^5|l,lll/mA8;l?j4aqjelEaYmcl~hGg$j7gNgO2v0!6D03ifihjA2LiYiVe%2o72gpmg6fk~8K6pl18TmllZl)8Gmpl(l5m=5W5=b5lg8Tmxlj8vdzm(77m*96b;l19jm/mqm;4OckbPl!ndmtm{6vn8cnmyl.lqnplsl@aw6*ltcsi|mbg#j6nvfTlxg,m7f!8@mP27mR17mT0.ig261yf6mZkp0)m$k4kcgiiVg9h/f5n37ga_cdlR0g9|7ommaIlg9?l8nfm;9?nim@n;nmn06X6Vn%d5mil1aPnan{o4m?n@m^aKn`oalgaPm crl-04l:ollrmDm)fyi0i}mdl|j0i?gTopmLnAnD8wnzmGoygSg*oBfWmH01jnlOcLm+l0b1l3n:l15fneb^oUl$5;o7oRlioi8v0L0h0B0L0L0c0J0(0J0o0c0k5#0(0L0W0n0k0%4 oNi9c=1S60d26a7eeup60Get0?h90N04.
# Tests
(insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)