Aller au contenu

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 :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013îC;=wSd*-gnh.+uerv6x,é9Otàkè5bE]l[f:D431(aRIp/)omq 72iyc8s_LPNT0050h0q0z0Q0$0H0*0Z0(0H0Q0*0*0e010z0$0T010406050*0p0X0X0Q0r0%040g0W0H0p140W0l0Z020Q0X0T0d0Z0R0q1e0r0Y0p0q0*050U1b1d1f1h190T04051M1F1P0U1M190h0$0s0|0~10120~0l0k0p0Q0k0q0j0T0%0z0m1o0Z0m0$0k0m0H1^0m0z17050@0E0H0q1Y0 11011@1_1{1_0z21231 0z0r1N1:0|1k0*0T0Q0l120#01251!010J0_0q0l1s0q1 2n2p2u272x232A0X2C040a0Z0-0r0W0T0W0*0$1n1p0=2l0r0r0q0(2X1F2E0l1N0U1:2-2h2j2i200h2G1#0$0l2z2U1 1V1X0}262`2|0l0W301 0T2$1N2+2-3d1a2o1p322v360r1e0H1 0Q1?2$0J12030+0+0(370q1{350W0j0O3E170Z0O1F0Q3e3h183g2F3j273l3n3p3r0q3t013v3x3z3B2}3E0j2s040Z0#3K3M2p3O2+2_013T0Q3o1N3q0m3s3u3w3y0=3%363)0N3H0N3/2*3N193?3R123_3{053}3 3Z413$2{3(3F0M3H0M4a1G4c3P3i1Z3S0W3m3`3V3~3X403#434p453F0D3H0D4v3d4d3h3@4h4F4l3!423A4L3D3F0t3H0t4R4x4e4A4g4C3U3|3W3Y4Z4o3C3)0!3H0!4,3;4T3Q4/3^4;4E4?4G4^4n4K4{3F0)3H0)502,524z33554D4i4k4H4m4J4#5d0j0x3H0x5i3=4U4f5n4=4j4@4I4!444%3E0:170O0:5A5k4V565p5H5s5J4$3)0O0O5O3J0U3L4b514y5T5o4X5r4_5c4q3E3+0O3.5)3:2,1Q3b1F302:0h2j2^5D4!2 1W1N3a0q3c3N5+5~4!6e2F0$0h123w2+5!3V6l6n5t5K6q0Z2K0q6t5Y5v5$2-5*4.5m0B170=0J6g6j5l2v0f3H6M5-5D0l0J172{1V0(0q6S6G2v16040P6$5C540l172e0q0Q0p6,535m6)0v6M0Z6T6.170(0$226#4w3;6 6`170V0K6M19765~3?6s016o3h3)3+5G7i5b5u5@2s6x2B6A4`7s1 5|0Z7B6~6%3S6J0q0E1m6}782v0W170e7K7E120X0$175Q7f3O7X5-7p0+6p3F474?7#6B5@477u2L7w5?4M0j7)3/7C7D6-5m6/042x0l7Q7|7M7O826_3k0E172J6^6O276)6+7Z7R3^6:0Q746?8c3@6)0V868d127N040j8s3@7T5O7d8o7#7%0j4s7*6m7j6u5Z4r2t6y7;7r7?8H7_7C7L276I040f1@238y6U7G7I0z8%548v020H0z0d7P7X7{877F7 2{8o5D6)7c7X7e3f7h8J7k2p3)4O8I8Q6v4N8O7v8K7,7?998U7`7B8W4g177T1{0q6@8@9n018v8?3d8^8t018f8}70040=8*8,5m8v0o9J3k17809E79048r9u8i8v0U0U9N278A045{4S8D957$7l4(6r9+9h5L4)7/6z9g7x7?4)6E3,9l9m8i8Y0$6L9V838`72749!8u178/8;aa8j046;8n8ha6126)0I9R9O049q0$9sap8e170G909)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$0z0p0r81bjbpbCa+bIbu1pbK0l5!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(170.1oc6b-6f0U6i5 6d616a1F0z64c`2?2.brc@0U621L6N3@2$0X0+0J0Q0B0q0+0m7)1x1z1B1D0Zca5~1S3O303@0Q0h0X1o2W0$1=2{0J8v1Ldrdtdv2X0j140z2f041x0(0m0q0rdN246Z1;0z0W7Tdj0Z2W0w0r0Q140s240K0Z0A2l0l2A0b2h751T1O040S0H0Z0*001*2W0Z2Z0Hd~0H0k4C2W0m2Le1242$dRdQdOe10$dN0WdVdX1C2G0$dj0n1Q7Yd30;1WdDdu0ldwdy6VdB1OexdFdxb;dIdK0,3qeddOefdS24e36YeidS0p0Zb+esd40,240(3`0(0pd{e200eT6!e1eWb+eXd#2W24dV1m3X0W0$0{dj0Hdj0{3y1d2z0@0$2$0*0n0Z0S720Z1=3a2S2U24054!3@1$1(1*1,1.1?1|2b1}2DcrbBa)bDc(bv9xaf9DbEbpct8+cH279LafaU8|fH548qaf9X9ZfL7S7U9%6Sc;3z04erdod40y0r0ve12pf3dPf70l0{fofq0{2Zfh0kd$1I2X2lf50Z230Z0cf.0~0Zf70Hg50=0{f6at0rgf0*0zg40$7T0z0w0qfb0ce$e(e*6~fm5Dfo1)1+1-0%ft2a1|1~d5b*fAcC2,c29KcxfC9BfGc7fI7HcugRbkcFfO9PfQgUfS7afU179Yaf9$9(c:6i0Z0T9sgl2o0rdAe~0Z0q0u0(0w0=0r0|0?0ze_0^gceRgne^fb0F1p3X0J0?f.2Vg4dk0=0p0udZ0l6Zdkfl3zfn2pfpgCfs291`gHfxbv7~fJf#g=0?gxhwgzhygBfrgEhCfvgI9vfPc%g;f%d|1oglf~2p0h0*g89sh40*dWeahv2ZhO1%hQgDgFhD2chFbA8)gXa#cE04cGgYbpaV3ff$0=3,g@1me10w2o10dPg43q0s3`h-gmgogreZd^0Lf:h50|0 ff3igvg5eShseUe:eXgLg~1p1ma)0*2pglg90~0r1+b$ebg4e-0lh70rimhadlhMh?54gAfqh`hThEgJ9FeYfX9wgQi2bf9GgWfKi6cwi4fF178gg(cz8{hYcD9W17a/i~j5hIfR9S9Ujc8404g-i?g/hJf%f)d@1Miuf@hmix0{3a0w0*f6h,g?2R220Cea2|d|242TjAg?iye%f-iJ2P1/1;0lh,gfiYgh0{0l00h$jNf{h80_iChch7fb0/0We{g|h+0Z0g0$iW1=0Qime01eez0Te*0webj!dW0Ef90Z0J0Hek0@iYf^jKjE0HjG24jAd$e00Q0Tg`eW90d@dq5DdseyeAhg0u1s0TdKdCkwdEezdGeJ2M0F0u1ykDd?dpewh@hzhR3y1pi.h}i:5m2I2z2B170-jT1=0c1oh/g50g1D2V1o6S6c6N5}1Nc=94cM7l0#3Gb@9`3Dl1cjcTcl3(l62t595Il43*l24a8i0k6)020k8;lmloln1vav9oi{9Ii?fEjm6W9%0n7WjifM170i0ig.fZ5P0#49919*k 97l17n3q7+lflSb`chla3*lc4Yl945lX9}9vlkaclrlp0dl:6~jfaqi8a#cqfDi^j8cr0XlA0#lCg+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@mP27mR17mT0hig261yf6mZkp0Qm$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;o7oRlioi8v0)0n0x0)0)0M0t0D0t0!0M0N5#0D0)0q0o0N0:4 oNi9c=1S60d26a7eeup60set0?h90*04.