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 :
.128013Eg[î r;)/(lDo4,6Ib=a+x5utP7e-h0TmnCk:SéNq.èy1cd32à 8_wvLpf*O9R]is050V0C0z0u0/0l0:0f0U0l0u0:0:0t010z0/0(010406050:0y0H0H0u0g0S040M0n0l0y140n0I0f020u0H0(0h0f0-0C1e0g0P0y0C0:050j1b1d1f1h190(04051M1F1P0j1M190V0/0$0|0~10120~0I0c0y0u0c0C0D0(0S0z0E1o0f0E0/0c0E0l1^0E0z17050@0s0l0C1Y0 11011@1_1{1_0z21231 0z0g1N1:0|1k0:0(0u0I120X01251!010)0_0C0I1s0C1 2n2p2u272x232A0H2C040a0f0A0g0n0(0n0:0/1n1p0=2l0g0g0C0U2X1F2E0I1N0j1:2-2h2j2i200V2G1#0/0I2z2U1 1V1X0}262`2|0I0n301 0(2$1N2+2-3d1a2o1p322v360g1e0l1 0u1?2$0)12030!0!0U370C1{350n0D0T3E170f0T1F0u3e3h183g2F3j273l3n3p3r0C3t013v3x3z3B2}3E0D2s040f0X3K3M2p3O2+2_013T0u3o1N3q0E3s3u3w3y0=3%363)0W3H0W3/2*3N193?3R123_3{053}3 3Z413$2{3(3F0o3H0o4a1G4c3P3i1Z3S0n3m3`3V3~3X403#434p453F0x3H0x4v3d4d3h3@4h4F4l3!423A4L3D3F0q3H0q4R4x4e4A4g4C3U3|3W3Y4Z4o3C3)0B3H0B4,3;4T3Q4/3^4;4E4?4G4^4n4K4{3F0Z3H0Z502,524z33554D4i4k4H4m4J4#5d0D0,3H0,5i3=4U4f5n4=4j4@4I4!444%3E0F170T0F5A5k4V565p5H5s5J4$3)0T0T5O3J0j3L4b514y5T5o4X5r4_5c4q3E3+0T3.5)3:2,1Q3b1F302:0V2j2^5D4!2 1W1N3a0C3c3N5+5~4!6e2F0/0V123w2+5!3V6l6n5t5K6q0f2K0C6t5Y5v5$2-5*4.5m0K170=0)6g3,5-5D0I0)172{1V0U0C6M6O5416040k6X6G3k172e0C0u0y6%5C6Z170p6M0f6Y5m0I170U0/226W4w3;6_2v6!0i0L6M19715~3?6s016o3h3)3+5G7d5b5u5@2s6x2B6A4`7n1 5|0f7w6^6(3S6J0C0s1m6@73270n170t7F7z120H0/175Q7a3O7S5-7k0!6p3F474?7W6B5@477p2L7r5?4M0D7!3/7x7y6:6`172x0I7L7@2v7I047K7S7?536`0s172J6/8474176$7U7M3^6*0u6 6-895l8b040i7|8a7H170D8q8m277O5O788l0f7W7Y0D4s7#6m7e6u5Z4r2t6y7,7m7.8G7;7x7G126I040#1@238v4V7B7D0z8$5D7 020l0z0h813d838w4g7_2{8B5D6!777S793f7c8I7f2p3)4O8H8P6v4N8N7q8J7%7.988T7=7w8V8g047O1{0C6.829m7 8=3N8@3@6!8d927}7A040=8)8+547 0v9I7^047`8|6;8o9M7~170j0j9T8x7P045{4S8B8D7g4(6r948K5v4)7*6z9f7s7.4)6E3,9k9l8f8X0/6L9t8f6{046}6 9Y128-8/0ha89n6+8k8e9D126!0d9Q9N9p0/9ram8n0.8 9%ah6k9-8E4}999?7-5L4}9;9a8L0DaA9j9|8Ua38`7{a2ai019vada4aoaqaR8ra98tad8y045(av9Cax6t8E5faB7l9b0D5faGaC8Q5La:aL7=9m8X4#a18?9ma4a68#aZ8^aT7J9w3;9y6P8h8j9sa,baakar9EaXbj6f8f6!at8Aaw1p9)963F5xa;9.5@5xa_a=aIbBa~aMb0172$0z0y0gaQb4aO9o0_apbq5,bw8Cay9*5M9,aH6C5NbGbD7.5P7u3LaMbf54b10`70bk9z17au4xb!by0I5!6D7j9-9g5L5#9d7+a`a?ca9`b?a bU9G7Eb93@aUcmbgbV9qbY2,b@5m9Ka%9!a*c0b|c25!7i3q7$9@c97o8OcdaI5`b;9{9}aS8XbObQbS9xb00U170O1ob{cB6f0j6i5 6d616a1F0z64c:2?2.8i232-621L6jba2$0H0!0)0u0K0C0!0E7!1x1z1B1D0fb 721S3O303@0u0V0H1o2W0/1=2{0)7 1Ldkdmdo2X0D140z2f041x0U0E0C0gdG246U1;0z0n7Odc8C0z0N0g0u140$240L0f0Y2l0I2A0e2h701T1O040r0l0f0:001*2W0f2Z0ld@0l0c4C2W0E2Ld`242$dKdJdHd`0/dG0ndOdQ1C2G0/dc0Q1Q7Tc|0;1Wdwdn0Idpdr6Qdu1Oeqdydqc3dBdD0%3qe6dHe8dL24d|6TebdL0y0fbpelc}0%240U3`0U0yd;d{00eM6Vd`ePbpeQdU2W24dO1m3X0n0/0{dc0ldc0{3y1d2z0@0/2$0:0Q0f0r6}0f1=3a2S2U24054!3@1$1(1*1,1.1?1|2b1}2DaSaWbWaYbTaScofva!019Abn8_9F7Cclfybacxcp54a49Pb!8}178pfKcw9V9XfS2va(9$c)6iekdhc}0+0g0pd`2pe|dIf00I0{fhfj0{2Zfa0cdV1I2X2le~0f230f0Jf+0~0ff00lg20=0{e ap0ggc0:0zg10/7OdT0Cf40JeVeXeZ6^ff5Dfh1)1+1-0Sfm2a1|1~c~8%crbXadfxcXbs8cfC9nck8*fW8s049LgSfDfNb|fP9SgWbb049Wcy17fZdg6i0f0(9rgi2o0gdte@0f0C0w0U0N0=0g0|0?0ze/0^g9eKgke.f40b1p3X0)0?f+2Vg1dd0=0y0w8C0I6Uddfe3zfg2pfigyfl291`gDfqfza4gQ6Xc*3z3,0?gthsgvhugxfkgAhyfogEb5aPhFg.0:1ogif{2p0V0:g59rh0hYg0hr2ZhM1%hOgzgBhz2chBbahDfFgRfHcn17gVh cqgYf!hHg/g;d`0N2o10dIg13q0$3`h*gjglgneSd.0mf-h10|0 f83igrg2eLhoeNe)eQfteP2z0f1mbW0:2pgig60~0g1+bQe4g1e$0Ih30gihh6dehKh/54gwfjh?hRhAgFcqeRg$gKbehUfE9Hi/i1adfBfOfLhVi^048ug$h|i@gZ9RfRi39JfUg*9#hWhHf$d-1Mipf;hiis0{3a0N0:e h)g/2R220Re32|d=242Tjpg/iteWf*g`1p0A1/1;0Ih)gciUge0{0I00hZjCf^h40_ixh8h3f40G0ne;g^h(0f0M0/iS1=0uihd_1ees0(eZ0Ne4jQdP0sf20f0)0led0@iUf=jzjt0ljv24jpdVd_0u0(g?eP8 d-dj5Ddlerethc0w1s0(dDdvkmdxesdzeC2M0b0w1yktd,dieph:hvhP3y1pi*h_i,542I2z2B17jI1:1=0J1ohYg20M1D2V1o6X6cc~5}1Nc+93a.7g0X3GbCc83*3Gb-k`k@5$5W5=a{k{c55|9m0c6!020c8:lalclb1vgOj3fGgLfw7Ja%6R9#0Q7Rj8fT040*0*jb5P0X49909(b$96k@cFb#b*3(lFcb9=bH4{lKl1lNlJ3*cPl7l9lfld0hlY6^i|9Ni5becRfzi:cu9m0Hlo0XlqgJ17lvlx0Flzl?gUlxbvcClDc3k@7:cGc7cIk{7)cLlR45m32t595Im7md9`lV17lYmmlfl#j59NhEi i2lkhCi~8?cv2v0U6D03iaicjp2LiUiReW2o6}dTl br4UcDk@8Sm5lImc8FlLmV3DmSme4Ymbm!mXmj8fd 6S6QmO72k;8J6pk@9imUcMlO0D4Ok}mhm}m$5;m(k{9il6m,lWlenalgl$8n9BmPmwi?lji;8ffJls6)9O8{nd2775l|fVnn9Zg+6@mz27mB17mD0Vib261ye mJkf0umMj`k2gfiRg6h,2Lm:7bmQm1k{9_c6mZnZmYm{lS9:mf5Xn0n!n7aSm-04dsnVgFmRaJb)n)mWaFmab.m)aFn,l26vk@aKn:fzl8mllXod8:mpngh{8(njl-nli_g$i{mqnol(olllj0aVojh~ohb}g#nwa#g(jbg,5jlCk=lEa@n|n4k@a^o0k~oLlQo1k{a}o9ban=0Z0Q0,0Z0Z0o0q0x0q0B0o0W5#0x0Z0C0v0W0F4 lB7UhG0=2-k,c.0$em6a79en0j0=g80:04.
# Tests
(insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)