Algorithmes de recherche naïve et dichotomique

I. Introduction⚓︎

🔎 La recherche d'un élément dans une liste est un problème fréquemment rencontré dans les algorithmes.
La fonction in de python fait cela :

Tester

II. Recherche naïve dans une liste⚓︎

Balayage

La façon la plus simple de chercher une valeur dans une liste est de parcourir un à un les éléments de la liste (de manière séquentielle). On compare les éléments à la valeur recherchée.

Parcours séquentiel version longue

Compléter la fonction appartient_1 dont les spécifications sont données.

Contrainte

Il est interdit d'écrire if element in tableau:

Évaluations restantes : 5/5

.128013tpwPenu)vglci,:rosfF38mL 0T/-à;q=6dyh_k[7(b519S]2a.4050J0f0b0Y0n0l0s0z0m0l0Y0s0s0H010b0n0c010406050s0h0x0x0Y0q0K040V0r0l0h0^0r0g050C0 1113150}0c04051l1e1o0C1l0}0J0n0j0-0/0;0?0/0g0k0h0Y0k0f0D0c0K0b0L1c0z0L0n0k0L0l1Q0L0b0{050(0R0l0f1x0:0=011P1R1T1R0b1Z1#1X0b0q1m1L0-180s0c0Y0g0?0X011%1z010t0*0f0g0Y0x0f1X1|1~231)261#292b0{0a0z0e0q0r0c0r0s0n1b0g0z0$1`0q0q0f0m2w1e2e0g1m0C1L2J1?1^1@1Y0J2g1A0n0g282t1X1u1w0.1(2T2V0g0r2Z1X0c2C1m2H2J2:0~1}2x2#242)0q120l1X0Y1O2C0t0?030M0M0m2*0f1T2(0r0D0A0D0T0{0z0T1e0Y2;2@0|2?2f2_1)2{2}2 310f33013537393b2W3e0D21040z0X3l3n1~3p2H2S013u0Y2~1m300L323436380$3E2)3G0v3i0v3M2G3o0}3Q3s0?3T3V053X3Z3A3#3D2U3F3f0!3i0!3.1f3:3q2^1y3t0r2|3U3w3Y3y3!3C3%403)3f0S3i0S462:3;2@3R3^4g3|3B3$3a4m3d3f0I3i0I4s483=4b3@4d3v3W3x3z4A3 3c3G0P3i0P4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3f0w3i0w4!2I4$4a2$4)4e3_3{4i3}4k4C4;0D0U3i0U4_3P4v3?4~4P3`4R4j4B3(4E3g0A0{0T0A5b4{4w4*505i535k4D3G0T3h045C5s495u4 4y524T4:413g3I0T3L0C3m3/4#5H5e4x4,4z4/555O0T3+5E3-5T3N4`5X4(5Z5h4-5j4U5(435E455-5V5/4L4}5=514.545l5B4p5E4r5~475W612`5v5K655z560T4G5E4I6c4t5:626h5!5L5$673f0T4X5E4Z6q4K5d5;6u5?5#665A6z4?5E4^6E6e6G6t5J6v6j5_4n3g585E5a6R2I1p2.1e2Z2M0J1^2R5e4B2Y1v1m2-0f2/3o5 1m4B6|2f0n0J0?362H5B3w73756L6l222k0f7b6k5(1X5~6f1)0N0{0$0t6~6s240d3i7s7m3@0t0{0Y0c1}0q0^280b0M3k6d6)7y010`040Q7x6T2`0{2)0x0R2C7S4%4}7P0p6~0z7t3t0R0{2U0b7!4|247P0o7)7+3@0{1:0f0Y0h7;3R7%7_7N0g7-041T0s7:7L717=1)7P0i847T1)0r0{0D020k0b0F8i7#2`870R0r18815e838c0}8c5H7a01762@3G3I5h8G6x6M3H7e2a7g8H7c5O8L7l8j0?7v3J0z8%8z4(0s0J0{020G0h0r8q8.8:8=8/8;8r8C818N0M773f5*8M748U7i6Z3+0z7f7h6Y5m928Y8t1)8+3i8%0z0y300t1c2E0n1N2C0g0j0r0n1$0B0q0h1$2u990r7X2C0z0f8a2y1~0,890b0f0o9I0b0z0u3U0s9C2U1c6~8D2=3Q8~900D5{939b5N6Z43998S9.5%9:7k5U7N9i8$8%0p7E2a9E9G0f0p8%7W7Y1$0E0z9P8a0f0q9#8}948I1~3G699-959cam8R2b9@6y0Dan9f8e0?9}9k0za013a27}7 a69O1$0J9M0z0/8/3a1#0z1N0j0f1a0z0s0Y9v0n0qaY0na3a9aY1$1?0r0haV0Zah8E9(aj8 8J4F79a_965m4G9=atap9/b09`8d3RaB9k0p2C0b0h0q0g0sa69z9Ba(a*9H9J9TaMbhaO0nae9R0%9U9W9Y2)1d8|a@4v9)a{0D6Bao8O564Xb28TbL5ObJ5-9$6}a^7b9*6ObK8V6Z4?bOau8PbZayb98,9~0z8o8=8p0Fb;0F0z7C7E7G0g7I0T0Q5R9R0O0v9R0S9R0I9Rc20z0vc50z0Sc90z0U0U0W8hbD9%bFa_9*6#b!a 3G58b(b49^5mcsb,5eba8%bk0fa?co72cqbH5qa}b)6l5ocxbQ6ZcN2J9{8Z01cEb:b?b^b^b`7D13b}b 0Q0X0Xc3cec70zchcbcdc6chcjclcIbVcpbXcM5Dctaq6z3hcSb#5m5Cb77`cZb.aC9V0+cHcnd0cKd2al6z8L308~cudqasbPda5B8X3mbU3O8FcLdp3g92dsa~d6dHdwcP5(9ecX9gaAdg9k8?8`dW8^8@8{6rbEdn8U9*0T9,dJdOcU9;9acyavd+b7aCde0g0{2C2sbhdk2:7*7N8l040H8saz010N0m0{di9Xc dDbWd)cMand-d=8P0T4pd9du3gax3md_7N7o049oag8ce2cYd{043a0f2bb~e73R0r8#2UeK5Y7|0Y1!7~80d%e88Bd$cJ2xbGdG6mcOem6lb1d;cTdb6n3MaCevcYex0n7reBd`0{eGeI8be1dee40He6e{857V9Fa98)7$0{7(dlegd1eie%bJele.5BbNe-dy6zbSeue=fue|04d}1ceef6cYf3eP4(ea0{cGef7Mfhak0g5BbZflfq3gb%fper0Tb+dBaidofN6zcsfQfVcwfUdL0TcBft8(ewd|0%bfbCf1f7fx0fd~fAeZ6}0C706*6{6,6^1e0b6/g72P2KeS1#2J6-8D0$0(0*0s04.

Parcours séquentiel version courte

🌵 Le problème de cette technique, c'est qu'on peut continuer à parcourir le tableau jusqu'au bout, pour rien, si on a trouvé l'élément avant la fin.

👉 Il est recommandé de faire une sortie anticipée de la boucle en utilisant le return

Compléter la fonction appartient_2 dont les spécifications sont données en utilisant une sortie anticipée.

Contrainte

Il est interdit d'écrire if element in tableau:

Évaluations restantes : 5/5

.128013tpwPenu)vglci,:rosfF38mL 0T/-à;q=6dyh_k[7(b519S]2a.4050J0f0b0Y0n0l0s0z0m0l0Y0s0s0H010b0n0c010406050s0h0x0x0Y0q0K040V0r0l0h0^0r0g050C0 1113150}0c04051l1e1o0C1l0}0J0n0j0-0/0;0?0/0g0k0h0Y0k0f0D0c0K0b0L1c0z0L0n0k0L0l1Q0L0b0{050(0R0l0f1x0:0=011P1R1T1R0b1Z1#1X0b0q1m1L0-180s0c0Y0g0?0X011%1z010t0*0f0g0Y0x0f1X1|1~231)261#292b0{0a0z0e0q0r0c0r0s0n1b0g0z0$1`0q0q0f0m2w1e2e0g1m0C1L2J1?1^1@1Y0J2g1A0n0g282t1X1u1w0.1(2T2V0g0r2Z1X0c2C1m2H2J2:0~1}2x2#242)0q120l1X0Y1O2C0t0?030M0M0m2*0f1T2(0r0D0T3e0{0z0T1e0Y2;2@0|2?2f2_1)2{2}2 310f33013537393b2W3e0D21040z0X3k3m1~3o2H2S013t0Y2~1m300L323436380$3D2)3F0v3h0v3L2G3n0}3P3r0?3S3U053W3Y3z3!3C2U3E3f0!3h0!3-1f3/3p2^1y3s0r2|3T3v3X3x3Z3B3$3 3(3f0S3h0S452:3:2@3Q3@4f3{3A3#3a4l3d3f0I3h0I4r473;4a3?4c3u3V3w3y4z3~3c3F0P3h0P4I3N4t3q4L3R4N4e4P4g4R3}4k4U3f0w3h0w4Z2I4#492$4(4d3^3`4h3|4j4B4:0D0U3h0U4^3O4u3=4}4O3_4Q4i4A3%4D3e0A0{0T0A5a4`4v4)4 5h525j4C3F0T0T5o3j0C3l3.4!485t4~4x514S4/403e3H0T3K5F3M4_5J5d4w4+4y4.545Q0T3*045*5r5Y4%5!5g4,5i4T5)425,445V5H5X4K4|5;504-535k5A4o5,4q5}465I602`5u5M645y550T4F5,4H6b4s5/616g5#5N5%663f0T4W5,4Y6p4J5c5:6t5=5$655z6y4=5,4@6D3N1p2.1e2Z2M0J1^2R5d4A2Y1v1m2-0f2/3n5~1m4A6+2f0n0J0?362H5A3v6=6@6K6k222k0f6}6j5)1X5}6e1)0N0{0$0t6-6r240d3h7e783?0t0{0Y0c1}0q0^280b0M5U2=7k010`040Q7j6F610{2)0x0R2C7D4$4|7A0p6-0z7f3s0R0{2U0b7L4{247A0o7Q7S3?0{1:0f0Y0h7Y3Q7O7%7y0g7U041T0s7X6c2I7(7z0{0i7=7E240r0{0D020k0b0F837M2`7^0R0r187/5d7;7}3o8n5J6|016^2@3F3H5g8r6w6L3G702a728s6~5Q8w77841)7h3I0z8O8k4%0s0J0{020G0h0r8b8V8X8Z8W8Y8c8n0}8p3P8y0M6_3f5+8x6?8F744m0D3*0z71735^8`8=8J8e1)8S3h8O0z0y300t1c2E0n1N2C0g0j0r0n1$0B0q0h1$2u8}0r7I2C0z0f7{2y1~0,7`0b0f0o9w0b0z0u3T0s9q2U1c6-8+7x4u8.8:0D5`8?8 5P8`428}8D9Y5(9!765G7y968N8O0p7q2a9s9u0f0p8O7H7J1$0E0z9D7{0f0q9P7/9T8u4n6{8@8z554o9$2b9(6x0D683-9-8T9/0z9;139?7+7-9`9C1$0J9A0z0/8W3a1#0z1N0j0f1a0z0s0Y9j0n0qaK0n9@9}aK1$1?0r0haH0Za58,9Sab8/a80D6m9X8^905l4Faf8Eac5Qa,937Z95an98ap2C0b0h0q0g0s9`9n9paQaS9v9x9Hayb4aA0na29F0%9I9K9M2)1d8*a6a(9U6Aa-a@8`4Wa=ah8Abu5V9Q6,8-bsa*6Nbv8G8`4=bza.9Z5lbJa`3Q9.a~898Z8a0FbX0F0z7o7q7s0g7u0X0Q5T9F0O0v9F0S9F0I9Fb/0z0vb=0z0Sb_0z0U0U0W82bqa$6;bH1~3F574P8.8_5l57bObwch9+6:a{0?bV98b70fa#9Rc96}9U5paabA6k5ncjbL5lcz2J9,8Kcpa}98b#cObZb%7p13b*b,0Q0X0Xb:b~b@0zc1b{b}b?c1c3c5cubFa%cxa*5BcAbP9)cG5CcEcg5A5CcIcnbUcM8O9J0+ctc7cv2xa7cb6y8w30cfa/5A21c|dhddcmbE6RbGc;dc3e8=dfa(c}6y8|8~c^ai5*cm7 cq8O8!8(dI8$8#8)6qc8daca0g5A9WdvcB5_8CagdB8A0T9W5Va~7 7a049ca48n7R7?0{3a0f2bb+8dco010r8M2Ud`4v7*0Y1!7,7.dP7:0{7Pd8c/cw8FcyakdVd!6kaedAck67cma~d)7yd+0n7dd/7 0gd=1#d^7|2:d:cKd|0{0H0He05Z7G9t9}8Q7Ne9c.dpc:eec=a,ehem6ya;elcF5Aa_3lepe*eD940?d+b0b2bpeCd*0m0{cseR7~dqeUds6zc@eY3ebye#dxf3dnbrdrdS6Mf1e$fcdkbQ5AbSe)98d*0{e:b3eJ4%0Ne^04d59Le{2J6/6S6*6U6%1e0b6XfE2P2Ke31#2J6V8+0$0(0*0s04.

III. La dichotomie⚓︎

1. Une première approche⚓︎

Je joue contre l'ordinateur

Question 1.

Exécuter le programme du jeu du nombre mystère. Faire quelques parties, expliquer la stratégie de l'ordinateur pour trouver le nombre mystère.

Solution

📋 Texte

A chaque fois, il se place au milieu.

Je joue contre l'ordinateur : suite

Question 2.

Lorsque le nombre est compris entre 1 et 100, en combien d'essais au maximum l'ordinateur trouve-t-il la solution ?

Solution

En 7 essais.

Question 3.

Et si le nombre mystère est compris entre 1 et 200 ?

Solution

En 8 essais.

2. La dichotomie⚓︎

La dichotomie

Le mot dichotomie vient du grec ancien διχοτομία, dikhotomia (« division en deux parties »).

La méthode de dichotomie fait partie des méthodes dites «diviser pour régner».

«dichotomie» se dit en anglais binary search.

3. Algorithme de recherche dichotomique⚓︎

Dichotomie, déroulement intuitif

on se place au milieu de la liste.
on regarde si la valeur sur laquelle on est placée est inférieure ou supérieure à la valeur cherchée.
on ne considère maintenant que la bonne moitié de la liste qui nous intéresse.
on continue jusqu'à trouver la valeur cherchée (ou pas)

Comprendre la méthode de dichotomie est relativement simple, mais savoir la programmer est plus difficile.

Pour des raisons d'efficacité, nous allons garder intacte notre liste de travail et simplement faire évoluer les indices qui déterminent le début et la fin de notre liste.

Une autre méthode pourrait être d'extraire à chaque étape une nouvelle liste (dont on espère qu'elle contient la valeur cherchée), mais la technique utilisée (le slicing de liste) consomme beaucoup trop de ressources.

Nous allons donc travailler avec trois variables :

indice_debut (en bleu sur le schéma)
indice_fin (en bleu sur le schéma)
indice_central, qui est égale à (indice_debut + indice_fin) // 2 (en rouge sur le schéma)

Dans cet exemple nous cherchons 14 dans la liste triée [2, 3, 6, 7, 11, 14, 18, 19, 24].

indices dichotomie

Nous allons faire se rapprocher les indices indice_debut et indice_fin tant que indice_debut <= indice_fin

4. Recherche d'appartenance⚓︎

Appartenance

Compléter la fonction appartient_dichotomique qui prend en paramètre une liste Python ma_liste et une valeur valeur. Cette fonction renvoie True si valeur est dans ma_liste et False sinon.

Évaluations restantes : 5/5

.128013tpwPen+u)vglci,:rosfF38mT 0/-;q=6dyh_k[7(b519S]2a4050I0f0b0X0o0m0t0A0n0m0X0t0t0G010b0o0c010406050t0i0y0y0X0r0J040U0s0m0i0?0s0g050C0}0 11130{0c04051j1c1m0C1j0{0I0o0k0+0-0/0;0-0g0l0i0X0l0f0D0c0J0b0K1a0A0K0o0l0K0m1O0K0b0_050$0Q0m0f1v0.0:011N1P1R1P0b1X1Z1V0b0r1k1J0+160t0c0X0g0;0W011#1x010u0(0f0g0X0y0f1V1`1|211%241Z27290_0a0A0e0r0s0c0s0t0o190g0A0!1^0r0r0f0n2u1c2c0g1k0C1J2H1;1?1=1W0I2e1y0o0g262r1V1s1u0,1$2R2T0g0s2X1V0c2A1k2F2H2.0|1{2v2Z222%0r100m1V0X1M2A0u0;030L0L0n2(0f1R2$0s0D0W0D0S0_0A0S1c0X2/2=0`2;2d2@1%2_2{2}2 0f3101333537392U3c3c3g0W3j3l1|3n2F2Q013s0X2|1k2~0K303234360!3C2%3E0w3g0w3I2E3m0{3M3q0;3P3R053T3V3y3X3B2S3D3d0Y3g0Y3*1d3,3o2?1w3r0s2`3Q3u3U3w3W3A3Z3|3#3d0R3g0R422.3-2=3N3;4c3^3z3Y384i3b3d0H3g0H4o443.473:493t3S3v3x4w3{3a3E0O3g0O4F3K4q3p4I3O4K4b4M4d4O3`4h4R3d0x3g0x4W2G4Y462!4#4a3=3@4e3_4g4y4-0D0T3g0T4=3L4r3/4`4L3?4N4f4x3!4A3e0B0_0S0B574@4s4$4|5e4 5g4z3E0S3f045y5o455q4{4u4~4P4,3}3e1 5A3H0C3k3+4X5D5a4t4(4v4+515K0S3%5A3)5P3J2G1n2,1c2X2K0I1?2P5a4x2W1t1k2+0f2-3m5R5+4x5~2d0o0I0;342F5x3u6567505h6a0A2i0f6d5v525z3*4H4_0M0_0!0u60634^220d3g6v5T4!0g0u0_0X0c1{0r0?260b0L1s0n1K0b0s0y0o0F0i0f6B6p220^040P6Z596D0_100L1R0t0b6Y433K6C4_6$0p6v0A6^2^0_0k3Q0f0i0r6)4Z6_0_0j6|6~1%6$0q6v0{6?5+3M6c01682=3E5M5d7l5Y6f3d1 6h286j7m6e5w7v1V5)0A7G6}6!3r0_2S6P0f6O0f0Q187b7J0;0s0_0G7T6*4_6U0_5n7i3n7)5D7s0L693d5$7r667A6l5K3%7x296k4Q7_7E3k7H7I7!6 047M0o0n7O241b7)8377227W047Y8d7c3:0Q0_2h766x7d0_6(7+7U3O6,0X6.0o6:6=2:8w6$7a8k8w8h0D7Z8f1%7$5A7g8q0A7-7/0D3 4M7-7^4j8W206i7}5J8#8X3I828l016r040d1N1Z8M8r3:7L0g7N7P7R0b8_3N8h020m0b0E8j2.8e8`8x868}888a2S925a7e8R8v4r8U7o4k6b7?7t7C0D4l7{7z9u524l2H81827H8/0g8|8~890g1;8D3m9b937X9j4!6$8u8E847K9e8~0!909T4_8h0h9(8587890L8b8S9k799,1%8h0C0C9^0;8P5O4p8S9p1|3E4C8Y9t7B524C9y8)5Z8#a68-9F7G9H707274356M0r729}018h999Pak046-6/6;9=9U0_0NaC4_9I9!9gao9M2AaG6#0_0V9m9X64a88V4Ta7ad7u0D4Tac7@7~8#aXahai8/8;0o6u8I9Y8{04711Zan9L1;ara=8N7V7Xav3K9Q5Uala`75a 9c9l7)7haT2va30g3E4/aYa(8*5i4/a%9A5Kbka,ai9G8w8;2A0b748c9aa.0n0_0z0r6XaS5 7kaV9q539saZ9v54bqa95K549D04bvb54!a/a;bD8waIa_730raLa}8^ba9R049597asb+amb9b)a?01bca19naU6d8V5mbQbmae5ic7bU8!cb5kbYb!8.b*9JaK9$7Sb=5aaub`cl9/a|aNcp4!9*as8P3ibda2bNa43d5yc8br8#cIcda)cb6n7Fbva.0_380t9Ob48/c144c3bgcFbicH7q2~8ZcO5x7w8(c9a!0S7qcRcib#aHct9hbCaw8J9Scxc|aJcuapcX2Gc{8g0_8Ld322cBbK6@bMc5bO5#cJbVcL7`c;cKcb7;c_da1%by0#bBas0MbF040v3QcWdh5+0C625,5}5.5`1c0b5;dQ2N2I0X1YdN0C5/7h0!0$0(0t04.

Déroulé à la main : v = 9 est-il dans t = [1, 3, 6, 9] ?

Ecrire le déroulé à la main. Voici le début à poursuivre de façon analogue :

indice_debut = 0
indice_fin = 3
condition du while : True
indice_centre = (0+3)//2 = 1
valeur_centrale = ma_liste[indice_centre] = 3
v == valeur_centrale → False
valeur_centrale < v → True
indice_debut = 2
condition du while : True
...

Solution

indice_debut = 0
indice_fin = 3
condition du while : True
indice_centre = (0+3)//2 = 1
valeur_centrale = ma_liste[indice_centre] = 3
v == valeur_centrale → False
valeur_centrale < v → True
indice_debut = 2
condition du while : True
indice_centre = (2+3)//2 = 2
valeur_centrale = ma_liste[indice_centre] = 6
v == valeur_centrale → False
valeur_centrale < v → True
valeur_debut = 3
condition du while : True
indice_centre = (3+3)//2 = 3
valeur_centrale = ma_liste[indice_centre] = 9
v == valeur_centrale → True
la fonction renvoie True

Déroulé à la main : v = 7 est-il dans t = [1, 3, 6, 9, 10] ?

Ecrire le déroulé à la main, comme dans l'exercice précédent

Solution

indice_debut = 0
indice_fin = 4
condition du while : True
indice_centre = (0+4)//2 = 2
valeur_centrale = ma_liste[indice_centre] = 6
v == valeur_centrale → False
valeur_centrale < v → True
indice_debut = 3
condition du while : True
indice_centre = (3+4)//2 = 3
valeur_centrale = ma_liste[indice_centre] = 9
v == valeur_centrale → False
valeur_centrale < v → False
indice_fin = 2
condition du while : False
la fonction renvoie False

👉 On voit dans cet exemple pourquoi l'instruction while indice_debut <= indice_fin : est absolument nécessaire.

5. Recherche d'indice⚓︎

Recherche

Compléter la fonction recherche_dichotomique qui prend en paramètre une liste Python ma_liste et un valeur valeur. Cette fonction renvoie son indice si valeur est dans ma_liste et None sinon.

Évaluations restantes : 5/5

.128013tpwPen+u)vglci,:rosf38m 0/-;q=6dyh_k[N7(b519S]2a4050G0f0b0W0o0m0t0y0n0m0W0t0t0E010b0o0c010406050t0i0x0x0W0r0H040T0s0m0i0=0s0g050A0|0~10120`0c04051i1b1l0A1i0`0G0o0k0*0,0.0:0,0g0l0i0W0l0f0B0c0H0b0I190y0I0o0l0I0m1N0I0b0^050#0P0m0f1u0-0/011M1O1Q1O0b1W1Y1U0b0r1j1I0*150t0c0W0g0:0V011!1w010u0%0f0g0W0x0f1U1_1{201$231Y26280^0a0y0e0r0s0c0s0t0o180g0y0Z1@0r0r0f0n2t1b2b0g1j0A1I2G1:1=1;1V0G2d1x0o0g252q1U1r1t0+1#2Q2S0g0s2W1U0c2z1j2E2G2-0{1`2u2Y212$0r0 0m1U0W1L2z0u0:030J0J0n2%0f1Q2#0s0B0v0B0R0^0y0R1b0W2.2;0_2:2c2?1$2^2`2|2~0f3001323436382T3b0B1~040y0V3i3k1{3m2E2P013r0W2{1j2}0I2 3133350Z3B2$3D0v3f0v3J2D3l0`3N3p0:3Q3S053U3W3x3Y3A2R3C3c0X3f0X3+1c3-3n2=1v3q0s2_3R3t3V3v3X3z3!3}3$3c0Q3f0Q432-3.2;3O3=4d3_3y3Z374j3a3c0F3f0F4p453/483;4a3s3T3u3w4x3|393D0N3f0N4G3L4r3o4J3P4L4c4N4e4P3{4i4S3c0w3f0w4X2F4Z472Z4$4b3?3^4f3`4h4z4.0B0S3f0S4?3M4s3:4{4M3@4O4g4y3#4B3d0z0^0R0z584^4t4%4}5f505h4A3D0R3e045z5p465r4|4v4 4Q4-3~3d3F0R3I0A3j3,4Y5E5b4u4)4w4,525L0R3(5B3*5Q3K2F1m2+1b2W2J0G1=2O5b4y2V1s1j2*0f2,3l5S5,4y5 2c0o0G0:332E5y3t6668515i6b0y2h0f6e5w535A3+4I4`0K0^0Z0u61644_210d3f6w5U4#0g0u0^2z0n0I0f0r6J0f0J1r6J0s0b0s0x0o0D0i0f6C6q210@040O6!5a6E0^0 0J1Q0t0b6Z443L6D4`6%0p6w0y6_2@0^0k3R0f0i0r6*4!6`0^0j6}6 1$6%0q6w0`6@5,3N6d01692;3D3F5e7m5Z6g3c1~6i276k7n6f5x7w1U5*0y7H6~6#3q0^2R6Q6O0Z0P177c7K0:0s0^0E7T6+4`6V0^5o7j3m7)5E7t0J6a3c5%7s677B6m5L3(7y286l4R7_7F3j7I7J7!70047N0o0n6O231a7)8378217W047Y8d7d3;0P0^2g776y7e0^6)7+7U3P6-0W6/0o6;6?2/8w6%7b8k8w8h0B7Z8f1$7$5B7h8q0y7-7/0B404N7-7^4k8W1 6j7}5K8#8X3J828l016s040d1M1Y8M8r3;7M0g7O6P0f7R0b8_3O8h020m0b0C8j2-8e8`8x868}888a2R935b7f8R8v4s8U7p4l6c7?7u7D0B4m7{7A9v534m2G81827I8/0g8|8~890g1:8D3l9c947X9k4#6%8u8E847L9f8~7Q7S8I9Z7V0^0h9U4`9J9#9h0J8b8S9l7a9.8g0^0A0A9{8O0o0^5P4q8S9q1{3D4D8Y9u7C534D9z8)5!8#aa8-9G7H9I71737534251:73a09+8iaw9e6.6:6=9^9V0^0LaE9/9K9=9M9OaI6$0^0U9n9Y65ac8V4Uabah7v0B4Uag7@7~8#aXalam8/8;0o6v9)8N8{04721YaraM0rava=9d8h0E9a9Qaoa^aq76a 3O9m7)7iaT2ua70g3D4:aYa(8*5j4:a%9B5Lbja,am9H8w8;2z0b758c9bb58789as9N2zaS607laV9r549taZ9w55bpad5L559E3Gbua.7Ma;bC8w9:a_740rbGau8^b95b95970Cazb)b7azbba59oaU6e8V5nbPblai5jc2bT8!c65lbXbu9GbD9gbF9%92b:4#b1b^aKbFa|9P3L9Rb;9,az8P3hbca6bMa83c5zc3bq8#cEc8a)c66o7GbZbw0^370tcr2FctaF047gczb~bfcBbhcD7r2}8ZcK5y7x8(c4a!5O80bYcdanb(co9ibBb48J9TckaJ9;cpatbId19|048Ld7a15mbJ6^bLc0bN5$cFbUcH7`c/cGc67;cNc_9*8:6H0!bAaz0K0n0^0M19cT7*2/0A635-5~5/5{1b0b5=dO2M2H0W1XdL0A5:7i0Z0#0%0t04.

IV. Exercice⚓︎

Une fête

Nicolas organise une fête, et demande à ses amis s'ils viendront. Dès qu'un ami lui répond favorablement, il l'ajoute dans liste_amis. Compléter le code ci-dessous afin de pouvoir déterminer si Vincent, Romain et Valérie ont décidé de venir (bien respecter les majuscules, minuscules et accents). La liste liste_amis est dans du code caché.

Vous devez absolument réaliser une recherche dichotomique et pas une recherche naïve. Attention, c'est à vous de créer ma_liste_amis qui est utilisée dans les tests. (Vous pouvez regader l'astuce plus bas, en cas de besoin)

Évaluations restantes : 5/5

.128013tpwPen+u)vglci,:rosfF38mT 0/-;q=6dyh_k[7(b519S]2a4050I0f0b0X0o0m0t0A0n0m0X0t0t0G010b0o0c010406050t0i0y0y0X0r0J040U0s0m0i0?0s0g050C0}0 11130{0c04051j1c1m0C1j0{0I0o0k0+0-0/0;0-0g0l0i0X0l0f0D0c0J0b0K1a0A0K0o0l0K0m1O0K0b0_050$0Q0m0f1v0.0:011N1P1R1P0b1X1Z1V0b0r1k1J0+160t0c0X0g0;0W011#1x010u0(0f0g0X0y0f1V1`1|211%241Z27290_0a0A0e0r0s0c0s0t0o190g0A0!1^0r0r0f0n2u1c2c0g1k0C1J2H1;1?1=1W0I2e1y0o0g262r1V1s1u0,1$2R2T0g0s2X1V0c2A1k2F2H2.0|1{2v2Z222%0r100m1V0X1M2A0u0;030L0L0n2(0f1R2$0s0D0Y0D0S0_0A0S1c0X2/2=0`2;2d2@1%2_2{2}2 0f3101333537392U3c0D1 040A0W3j3l1|3n2F2Q013s0X2|1k2~0K303234360!3C2%3E0w3g0w3K2E3m0{3O3q0;3R3T053V3X3y3Z3B2S3D3d0Y3g0Y3,1d3.3o2?1w3r0s2`3S3u3W3w3Y3A3#3~3%3d0R3g0R442.3/2=3P3?4e3`3z3!384k3b3d0H3g0H4q463:493=4b3t3U3v3x4y3}3a3E0O3g0O4H3M4s3p4K3Q4M4d4O4f4Q3|4j4T3d0x3g0x4Y2G4!482!4%4c3@3_4g3{4i4A4/0D0T3g0T4@3N4t3;4|4N3^4P4h4z3$4C3e0B0_0S0B594_4u4(4~5g515i4B3E0S3f045A5q475s4}4w504R4.3 3e3G0S3J0C3k3-4Z5F5c4v4*4x4-535M0S3)5C3+5R3L4^5V4$5X5f4+5h4S5$415C435+5T5-4J4{5:4 4,525j5z4n5C4p5|455U5 2^5t5I635x540S4E5C4G6a2:1p2,1c2X2K0I1?2P5c4z2W1t1k2+0f2-3m5}1k4z6F2d0o0I0;342F5z3u6M6O645y3d3f0A2i0f6U6i5$1V5|6d3r0_100L1R0t0b0f0L280o0t6H0A5.4{0s0_0G6{6}2^0Q0_0t4b6=0I6H731%0^040P7b6+3=0_6:6=6@0y6_7h5b4$7e0j6H0{6b2G5F6T016P2=3E3G5f7A5!653d1 6Z286#7B6V547F5+7w2:3O7H0L6Q3d5(7G6N7P6%4l0D3)7M296$5@7*7#7T7q6L7%7C1|3E5_7$7/5L7*417-7O7I6W3c6)5S7i010M0_0!0u7@4`220d3g8g4u0u0_0X0c1{0r0?260b0L1s0n1K0b0s7o0F0i0f8l5c7e7g7x6K8h6,046.7l8F8K7c0;7e0p728a0g0_0k3S0f0i0r8G7s0_7u8K6|8a7e0q7v8l7X7Z0D677~7(7:5k4n837 5#7*8{5+0A978/7r600_2S8x6?0!0Q188X9a226 04718.8T017o0_5p8K7U6G7W7_7Y7D4D6S9z7)5k4E918}809G883H989q8Z049d0o0n6?241b9p8a9m9o2.994#6075042h8*4{8I9-2^6-0X6/6_6=9:7d8,9j9(9l0_0D9}8M0;9s5C8?8S9y6U8_4V4O7X9F4U206!927J0Dac3K989%a38b0_0d1N1Za24u9c0g9e8w0f9h0baw5c9m020m0b0E9#3mapax9Raz9T9V2SaF8+048=9v8@9z8_4;ad9E8~3E4;9I8554a%anao9O8YayaA9U0g1;8R9$9q9!aV9.0_8J7V9k8N9S9UaBaDb19 040hbcb7aRb99W9`8U9|9Yb60;9m0C0Cbga40o0_5Q4ra!aa9B559Daj8656a-7Q5M562H3ka=a?bp3Q8!8$8(358u0r8$bu01b0bo9~8N8P9^a}9xbQ7e0NblbRaQa_bWb+3M9q7e0Va7b57^bB7{6X5ma(bF6j5mbIafc29MbO979q8c9R8fb$aq9Q8#1ZbUa`1;bYci3P9!aM3MaO5WbScm8)cr8H0_aYbza84t8^bC5AbE9J935kcKc8a*6X5Ba;ccbPb%0;cf2A0b8(9Xa~8a0M0n0_0z0r8Eb}b,b 7P8_5PcLa.5$7LaicMakc^bM9NbOce9cchc(bQckbT0rbVa{bXavcB4$aHaJ0EbZd9czbZ8;c:b_a9c?cJ7#2~aecR3e7,c}c`7*5%cbcVcWcja^aSba9idg6~70dldJb9co2AbZ9mbfdN22a53iaZcGc=7`0g5z7}dwa)9Kd+ah7Nc55^dFd3c)0_380tb^2GcwaWcE46d%2vcIc13e8{d-d?dD90dBbJecd^dG9PdRaTc%aNa dPdYbhb?ddd~3Heo04a1eqbv5ndq7ydsd)5z6l8|dCcO9Heec93eeH96dH3PcZ0#c$bZc*0_0v3Sd}eC2H6J1n6r0C6t1c0b6ve-2N2I0X1Y6E6s6B7w0!0$0(0t04.

Astuce

N'y-a-t-il pas une condition sur la liste dans laquelle on réalise la recherche dichotomique ?

Solution pour Vincent, Romain et Valérie

🐍 Console Python

>>> appartient_dichotomique(ma_liste_amis, "Vincent")
False
>>> appartient_dichotomique(ma_liste_amis, "Romain")
False
>>> appartient_dichotomique(ma_liste_amis, "Valérie")
True
>>>

V. Bilan⚓︎

A savoir par 💚 (cliquer)

🐍 Script Python

def recherche_dichotomique(ma_liste, valeur) :
    indice_debut = 0
    indice_fin = len(ma_liste) - 1
    while indice_debut <= indice_fin :  # (1)
        indice_centre = (indice_debut + indice_fin) // 2  # (2)
        valeur_centrale = ma_liste[indice_centre]
        if valeur_centrale == valeur :
            return indice_centre
        if valeur_centrale < valeur :
            indice_debut = indice_centre + 1  # (3)
        else :
            indice_fin = indice_centre - 1  # (4)
    return None

Il faut bien <= et pas <
Il faut une division entière donc // et pas /
👉 On cherche à droite
👈 On cherche à gauche

Prenez le temps de lire les commentaires (cliquez sur les +)

VI. Crédits⚓︎

Auteurs : Gilles Lassus, Fabrice nativel, Jean-Louis Thirot, Valérie Mousseaux et Mireille Coilhac