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
🐍 Console Python
>>> 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

.128013f6S=d-èNpg2mRC 8P5)kLus_hq0:4yrE./oTxDbc1w937ve[l,O*+tài]né;Ia(î050f0V0$0.0(0X0x0p0O0X0.0x0x0e010$0(0j010406050x0w0m0m0.0F0E040d0J0X0w140J0*0p020.0m0j0,0p0n0V1e0F0A0w0V0x050I1b1d1f1h190j04051M1F1P0I1M190f0(0U0|0~10120z0(0k0z0X1%0z0$17050@0N0X0V1Y0 11011$1(1*1(0$1:1=1.0$0F1N0$0z0|1k0x0j0.0*120l011@1!010b0_0V0*1s0V1.2a2c2h1_2k1=2n0m2p040a0p0r0F0J0j0J0x0(1n1p0=280F0F0V0O2K1F2r0*1N0I262W2325241/0f2t121*0*2m2H1.1V1X0}1^2*0(2,0*0J2:1.0j2P1N2U2W311a2b1p2=2i2`0F1e0X170p0P2T3518342s371_393b3d0l3g2c3i2U2)013n0.3c040p0S3r2V193u3l123x3z0p0D3D3t353v3J3d0s3N3F3P3H3w0J3a3y3d0c3U3j361Z3m3Z3o3A0T3(3G3+3I3-3#3A0q3;3W3?3Y3!3K0R3|3k3~3R040P0B433*2?3 3.0P3f1G3h3V444c460P3q4h3s1Q2 1F2:2Z0f252(3X0O2{2z0;1W1N2~0V303h3N054A0=4I4k2i0u170=0b4K3=4c0Q3d4V3}4l0b172^1V0O0V4!4P1_16040/4-4b3817200V0.0w4?3v4:0Y3N0p3)3Q170O0(1;4,4p2V543X4:0t0C3U0p5j534W4^040=0N1m525d3~0J170e5s5m1_0m0(17495b185k5l4#5n2k0*5y5J1_5v045x5F5I4.3I0N172w4~5e174=5F5t4l4_0.594|5!3~5f5N5V015Q0g5=4@5A5C475i5k5)4Q170Q1$1=5`555o0V5q0$673X5Q020X0$0,5S315U5{3I175L5/4c4:5h5F065H5H613m175B1*0V4}5T6z125Q6k3h6m4 5$6r5n5p5r6G5z6I170#6d456p2^6P4/170t6Y4c5Q0I0I6*2i5B174o316w6x5j6H014R040(4U6T5O6o0457596/5P176g6i77734`5.5(6U014:0W6$736C0(6E7l7i170)6u6@6_6_6{0*6!5M715?6J7c3w6B0_7o6F6l6{5^7F6;5~6v7w6M3X6}0V1*707L7h7z7458667C6n5@5w6K3s7T6Z047e7K4J7h7j7q7#7n7p7g727r047t5 7S6`7h6}2P0$0w0F7B7Z7 7{7I7}7v7w6{7V0`5a337^177u4i84607!4S6a6S8d7D5w7F8f6D7?7.7M6W7O5}4g8i857 870?8a8c6L8k0O170i1o8n4i1F4M4H4r8%0I4u1F0$4w8,2$2X5,1=2W4u1L4O7*2P0m0y0b0.0u0V0y0z0S171x1z1B1D0p8r4q1S3i2:3v0.0f0m1o2J0(1o0p2^0b5Q1L9h9j9l2K0g140$21041x0O0z0V0F9E1?4*0z0J0$0J5B999p0$0+0F0.140U1?0C0p0%280*2n0:235a1T1O040-0X0p0x000.0k2J0p2M0X9?0X0k3Z2J0z2y9`1?2P9I9H9F9`0(9E9M9O0(9Q3laf1C0H1Q3i8*4E1U1W9u9k0*9m9o9q9s1Oar9w9n0*9y2J9B0v0.0pa69Fa89J1?9|4)ab9J0w0p7|6F9,1M0v1?0O3y0O0w9:9{00aP4+9`aSaUaT9T2J1?9N1m0V9r0(0{990X990{4A1d2m0@0(2P0x0H0p0-570p9o2~2F2H1?4L4B3v1{1)1+1-8`68aU7F7E7)6N4;7`8w6bbs8Ibu3X7#6q7~5?5;bC5u176-8J6=4K0I8$04ak9e8_0Z0F0Y9`2cb09Gb40*0{0~0*0k9@9a2Mbe0k9U1I2K28b20p1=0p0obY0~0pb40Xb{0=0{b37o0Fc50x0$b`0(5B9S0Vb80oaZa#a%538$bk1+1}1,2q8e7H8EbA5R7F4:5%8oct69bzbJ6+bB8z7*bE6#bG7*bIcI3v6,6.cF6:5}6?4JbQ4B3A0j6Ecb2b0Fa`c50L0O0+0=0F0|0?0$a?0^c2aNcda=b80G1pa_0b0?bY2Ib`b.6E0L9p0*4*9abi2M3Xblcqbo7yby8ycXbR0p0?cmbjdfcpbncs5?cK8S9ddn0x1ocbb;2c0f0xb~6Ec:dBb_ddaZ3~dgdubpbDdk6ccT78046XdW73bF33cY4N0pc#1m9`0+2b109Gb`aH0U3ydJcccecgal8_0Mb!c;0|0 bc36ckb{aOdaaQa-aT8gaS2m0p1m7I0x2ccbb 0~0F0kd_a)2^c?0Fd@c_9bdqdedPdt1~dvcJcu7Jcw7-2V7/5*cDdl8G7h5QdZcP5#bwcM68d$8TeP175_d!7GeMdVcBbH6(cwbMe$7PcWdzcZbTaW04d b(d5e20{2~0+0xb3dId*2E1;0ha32,9;1?2Gf1d*e3a!bXdo1p0r0E261odIc50*149G0{0*00dCfe0{2Mc1e7c{c?b80K0Ja^c*bY0d0(b`fv1p0.d@9_1eat0ja%0+a4ft9O0Nb60p0b0X9M0@fqb)fbf50Xf71?f19U9_0.0jc(aS6u9,9g3X9iasauc 0L1s0j9B9tf 9vat9x9z9B0G0L1yg69+9faqds1|dR6{2v2m2o172B0o1odBb{fkfmdy5c4G8`324JbR6{0k4:020k6igLgNgM1vbxe(eH7O4%040l0H5EeSbK040!0!bN470B0l3C6vgIgKgQgO0,g?53eVdT04eX7.8N8Acxe/gWgYg!eY7 5Qg(g*48g-cweRh65?7P8L8!7hgJ79g=hn6ig_e*eEgTe$eQ8C7A52eK2i0O0P1703d-d/f12yfqa4e22b579S4a3v9 4(0*7Yhj7 hl04g?hZgQhq7@7 czgS6Re)hf7*hve$dx7qcOh-cQbLg*e;eJhz1_hBhDhF1^1yb3hKa!hM2JfWf(c8hKb dL2yhP3XhR6~hTig3~hXh!gPhph*8xh,eOh7cHh@eTcAh%dwhxhue!hwhthrbv6)iD04cSg#4ce:il4cii0q0H0R0q0q0D0c0s0c0T0D0S4f0s0q0V0#0S0B3:g/d(8)gD4taoi^0Uam8^4t0?c^0x04.