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

.128013cPw-7 sSf.bgn3T8k9]vei;(h4l,LFmdo0qp65_:2)à=tay1/[ur050G0v0T0U0w0B0h0g0b0B0U0h0h0S010T0w0K010406050h0Z0F0F0U0!0V040i0H0B0Z0^0H0n050X0 1113150}0K04051l1e1o0X1l0}0G0w0u0-0/0;0?0/0n0m0Z0U0m0v0e0K0V0T0z1c0g0z0w0m0z0B1Q0z0T0{050(0l0B0v1x0:0=011P1R1T1R0T1Z1#1X0T0!1m1L0-180h0K0U0n0?0P011%1z010j0*0v0n0U0F0v1X1|1~231)261#292b0{0a0g0c0!0H0K0H0h0w1b0n0g0$1`0!0!0v0b2w1e2e0n1m0X1L2J1?1^1@1Y0G2g1A0w0n282t1X1u1w0.1(2T2V0n0H2Z1X0K2C1m2H2J2:0~1}2x2#242)0!120B1X0U1O2C0j0?030N0N0b2*0v1T2(0H0e0I0e0W0{0g0W1e0U2;2@0|2?2f2_1)2{2}2 310v33013537393b2W3e0e21040g0P3l3n1~3p2H2S013u0U2~1m300z323436380$3E2)3G0o3i0o3M2G3o0}3Q3s0?3T3V053X3Z3A3#3D2U3F3f0A3i0A3.1f3:3q2^1y3t0H2|3U3w3Y3y3!3C3%403)3f0M3i0M462:3;2@3R3^4g3|3B3$3a4m3d3f0L3i0L4s483=4b3@4d3v3W3x3z4A3 3c3G0f3i0f4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3f0q3i0q4!2I4$4a2$4)4e3_3{4i3}4k4C4;0e0s3i0s4_3P4v3?4~4P3`4R4j4B3(4E3g0I0{0W0I5b4{4w4*505i535k4D3G0W3h045C5s495u4 4y524T4:413g3I0W3L0X3m3/4#5H5e4x4,4z4/555O0W3+5E3-5T3N4`5X4(5Z5h4-5j4U5(435E455-5V5/4L4}5=514.545l5B4p5E4r5~475W612`5v5K655z560W4G5E4I6c4t5:626h5!5L5$673f0W4X5E4Z6q4K5d5;6u5?5#665A6z4?5E4^6E6e6G6t5J6v6j5_4n3g585E5a6R2I1p2.1e2Z2M0G1^2R5e4B2Y1v1m2-0v2/3o5 1m4B6|2f0w0G0?362H5B3w73756L6l222k0v7b6k5(1X5~6f1)0r0{0$0j6~0g6s2`0j0{0U0K1}0!0^280T0N3k6d6)7m0?0`040y6~7u3t0{2)0F0l2C7O7J017L0O7s7P3@0l0{2U0T7W6T247L0C7#7X0n0{1:0v0U0Z7,4%4}7Z7;7-3t7(041T0h7+7H714|7.0{0Q807}240H0{0e020m0T0x8e8a820{0l0H187|8p7K0{7!880}885H7a01762@3G3I5h8E6x6M3H7e2a7g8F7c5O8J7l810?0d3i0g8#8v3R0h0G0{020J0Z0H8m8,8.8:8-8/8n8A8%8L0N773f5*8K748S7i6Z3+0g7f7h6Y5m908W8f1)8)8!8#0D300j1c2E0w1N2C0n0u0H0w1$0p0!0Z1$2u970H7T2C0g0v862y1~0,850T0v0C9F0T0g0E3U0h9z2U1c6~8B2=3Q8|8~0e5{91995N6Z43978Q9+5%9-7k5U7X9g3J8#0g0O7A2a9B9D0v0O8#7S7U1$0R0g9M860v0!9Y8{928G1~3G699*939aak8P2b9;6y0eal9d8w019`9|9}9 0Faa0U1!7_0Za49L1$0G9J0g0/8-3a1#0g1N0u0v1a0g0h0U9s0w0!aY0wa1a7aY1$1?0H0ZaV0kaf8C9#ah8}8H4F79a_945m4G9/aran9,b09@898(8*9{8#0O2C0T0Z0!0n0ha49w9ya(a*9E9G9QaMbiaO0wac9O0%9R9T9V2)1d8`a@4v9$a{0e6Bam8M564Xb28RbM5ObK5-9Z6}a^7b9%6ObL8T6Z4?bPas8Nb!awb99h0g8k8:8l0xb;0x0g7y7A7C0n7E0W0y5R9O0Y0o9O0M9O0L9Oc20g0oc50g0Mc90g0s0s0t8dbE9!bGa_9%6#b#a 3G58b)b49=5mcsb-5eaz9|bl0va?co72cqbI5qa}b*6l5ocxbR6ZcN2J9^8XaybaaAb^c$b?b`7z13b}b 0y0P0Pc3cec70gchcbcdc6chcjclcIbWcpbYcM5Dctao6z3hcSb$5m5Cb77$cZb/9S0+cHcnd0cKd2aj6z8J308|cudpaqbQda5B8V3mbV3O8DcLdo3g90dra~d6dGdvcP5(9ccX9e0?cE8#8;8^dV8?8=8_6rbFdm8S9%0W9)dIdNcU9.98cyatd*b7aAde7?042C2sbidj2:7t7X8h040S8o3R0r0b0{dh9Uc dCbXd(cMald,d;8N0W4pd9dt3gav3md^7X7o049lae88e1cYd`3a0v2bb~e65e0H8Z042UeH5;7@aF1#7`8%5e7 dkeed1egdF6mcOek6lb1d:cTdb6n3MaAetcYev0w7rezd_0{eDeF87e0dee30Se5e^7=7R9Ca7eT4(eVd#cJ2xbHe!bKeje+5BbOe*dx6zbTese/fqe_d{0vd}ecf3cYf0eN4}e80{cGed7IeYai0n5Bb!fhfm3gb(flep0Wb,dAagdnfJ6zcsfMfRcwfQdK0WcBfp8$eu0{bebgbDe~f4ftfvd 488C0X706*6{6,6^1e0T6/g22P2KeQf 0X6-8B0$0(0*0h04.

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

.128013cPw-7 sSf.bgn3T8k9]vei;(h4l,LFmdo0qp65_:2)à=tay1/[ur050G0v0T0U0w0B0h0g0b0B0U0h0h0S010T0w0K010406050h0Z0F0F0U0!0V040i0H0B0Z0^0H0n050X0 1113150}0K04051l1e1o0X1l0}0G0w0u0-0/0;0?0/0n0m0Z0U0m0v0e0K0V0T0z1c0g0z0w0m0z0B1Q0z0T0{050(0l0B0v1x0:0=011P1R1T1R0T1Z1#1X0T0!1m1L0-180h0K0U0n0?0P011%1z010j0*0v0n0U0F0v1X1|1~231)261#292b0{0a0g0c0!0H0K0H0h0w1b0n0g0$1`0!0!0v0b2w1e2e0n1m0X1L2J1?1^1@1Y0G2g1A0w0n282t1X1u1w0.1(2T2V0n0H2Z1X0K2C1m2H2J2:0~1}2x2#242)0!120B1X0U1O2C0j0?030N0N0b2*0v1T2(0H0e0W3e0{0g0W1e0U2;2@0|2?2f2_1)2{2}2 310v33013537393b2W3e0e21040g0P3k3m1~3o2H2S013t0U2~1m300z323436380$3D2)3F0o3h0o3L2G3n0}3P3r0?3S3U053W3Y3z3!3C2U3E3f0A3h0A3-1f3/3p2^1y3s0H2|3T3v3X3x3Z3B3$3 3(3f0M3h0M452:3:2@3Q3@4f3{3A3#3a4l3d3f0L3h0L4r473;4a3?4c3u3V3w3y4z3~3c3F0f3h0f4I3N4t3q4L3R4N4e4P4g4R3}4k4U3f0q3h0q4Z2I4#492$4(4d3^3`4h3|4j4B4:0e0s3h0s4^3O4u3=4}4O3_4Q4i4A3%4D3e0I0{0W0I5a4`4v4)4 5h525j4C3F0W0W5o3j0X3l3.4!485t4~4x514S4/403e3H0W3K5F3M4_5J5d4w4+4y4.545Q0W3*045*5r5Y4%5!5g4,5i4T5)425,445V5H5X4K4|5;504-535k5A4o5,4q5}465I602`5u5M645y550W4F5,4H6b4s5/616g5#5N5%663f0W4W5,4Y6p4J5c5:6t5=5$655z6y4=5,4@6D3N1p2.1e2Z2M0G1^2R5d4A2Y1v1m2-0v2/3n5~1m4A6+2f0w0G0?362H5A3v6=6@6K6k222k0v6}6j5)1X5}6e1)0r0{0$0j6-0g6r2`0j0{0U0K1}0!0^280T0N5U2=780?0`040y6-7g3s0{2)0F0l2C7z7u017w0O7e7A3?0l0{2U0T7H6F4|7w0C7M7I0n0{1:0v0U0Z7T4$7V0{7L6c2I7f7Z7P041T0h7S7/6:4{247w0Q7Y7U240H0{0e020m0T0x817+2`7?0l0H187*7}1)7K6-0}7{5J6|016^2@3F3H5g8q6w6L3G702a728r6~5Q8v77821)0d3h0g8N8i3Q0h0G0{020J0Z0H898U8W8Y8V8X8a7{8n7t4u8x0N6_3f5+8w6?8E744m0e3*0g71735^8_8;8I8c1)8R8M8N0D300j1c2E0w1N2C0n0u0H0w1$0p0!0Z1$2u8|0H7E2C0g0v7_2y1~0,7^0T0v0C9u0T0g0E3T0h9o2U1c8m8P8-8/0e5`8=8~5P8_428|8C9U5(9W765G7I953I8N0g0O7m2a9q9s0v0O8N7D7F1$0R0g9B7_0v0!9N8o3P9P8t4n6{8?8y554o9Y2b9!6x0e683-9)8S9+8N9.139:7$7(9@9A1$0G9y0g0/8V3a1#0g1N0u0v1a0g0h0U9h0w0!aI0w9;9`aI1$1?0H0ZaF0ka28+6;a98.a60e6m9T8@8 5l4Fad8Daa5Qa*928j0?9*9,9-2C0T0Z0!0n0h9@9l9naOaQ9t9v9Fawb2ay0w9 9D0%9G9I9K2)1d8)9Oa$9Q6Aa+a=8_4Wa:af8zbs5V8*6,a4bqa(6Nbt8F8_4=bxa,9V5lbHa^8Qala|878Y880xbV0x0g7k7m7o0n7q0P0y5T9D0Y0o9D0M9D0L9Db-0g0ob:0g0Mb@0g0s0s0t80boa38,bF1~3F574P8-8^5l57bMbucf9%7|bS960gb50vaZbDc76}9Q5pa8by6k5nchbJ5lcw2J9(8Ja`bT9,bZcLbXb#7l13b(b*0y0P0Pb.b|b=0gb b_b{b;b c1c3cr6RbEcua(5BcxbN9#cD5CcBce5A5CcFcl5da{9,9H0+cqc5a!2xa5c96y8v30cda-5A21c_dedackbCc,ct8Ecv8;dca$c`6y8{8}c=ag5*ck7N01d08N8Z8%dF8#8!8(6qc6a#c.d93e9Sdrcy5_8Baedx8z0W9S5Va|dB7a049aa17{7;cH3R0{3a0v2bb)8ba_010H8L042Ud^4v7#0U1!7%7)dMd_8ld5csdNdoc/aidSdX6kacdwci67cka|d$7Id(0w7dd,dB7!04d;d?7`2:d-930?84040S0Sd 5Z7C9r9`8P5de8dLd60gd80n5Aa*efek6ya/ejcCeVemene)d%0{a~b0bneAd%0b0{cpc+2I8pc8eU6ybseXe$e}dVa;f03ebA3ldle_c-ecdP0WbHe dt3ebLe#fgfde(8Oepe,0%e.eI4%0re=04d29Je^2J6/6S6*6U6%1e0T6XfG2P2Ke21#2J6V8n0$0(0*0h04.

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

.128013cPw-7 sSfbgn3T8k9+]vei;(h4l,Fmdo0qp65_:2)=tay1/[ur050F0v0R0S0w0B0h0g0b0B0S0h0h0Q010R0w0J010406050h0X0E0E0S0Y0T040i0G0B0X0?0G0m050V0}0 11130{0J04051j1c1m0V1j0{0F0w0u0+0-0/0;0-0m0l0X0S0l0v0e0J0T0R0z1a0g0z0w0l0z0B1O0z0R0_050$0k0B0v1v0.0:011N1P1R1P0R1X1Z1V0R0Y1k1J0+160h0J0S0m0;0O011#1x010j0(0v0m0S0E0v1V1`1|211%241Z27290_0a0g0c0Y0G0J0G0h0w190m0g0!1^0Y0Y0v0b2u1c2c0m1k0V1J2H1;1?1=1W0F2e1y0w0m262r1V1s1u0,1$2R2T0m0G2X1V0J2A1k2F2H2.0|1{2v2Z222%0Y100B1V0S1M2A0j0;030M0M0b2(0v1R2$0G0e0O0e0U0_0g0U1c0S2/2=0`2;2d2@1%2_2{2}2 0v3101333537392U3c3c3g0O3j3l1|3n2F2Q013s0S2|1k2~0z303234360!3C2%3E0n3g0n3I2E3m0{3M3q0;3P3R053T3V3y3X3B2S3D3d0A3g0A3*1d3,3o2?1w3r0G2`3Q3u3U3w3W3A3Z3|3#3d0L3g0L422.3-2=3N3;4c3^3z3Y384i3b3d0K3g0K4o443.473:493t3S3v3x4w3{3a3E0f3g0f4F3K4q3p4I3O4K4b4M4d4O3`4h4R3d0p3g0p4W2G4Y462!4#4a3=3@4e3_4g4y4-0e0r3g0r4=3L4r3/4`4L3?4N4f4x3!4A3e0H0_0U0H574@4s4$4|5e4 5g4z3E0U3f045y5o455q4{4u4~4P4,3}3e1 5A3H0V3k3+4X5D5a4t4(4v4+515K0U3%5A3)5P3J2G1n2,1c2X2K0F1?2P5a4x2W1t1k2+0v2-3m5R5+4x5~2d0w0F0;342F5x3u6567505h6a0g2i0v6d5v525z3*4H4_0q0_0!0j60040g5T4!0m0j0_0S0J1{0Y0?260R0M1s0b1K0R0G0E0w0I0X0v6v6y4_0^040y6V6p2^0_100M1R0h0R6U433K6W226Y0C6v6x6$3r0_0u3Q0v0X0Y6#594!6Y0P6^6;1%6Y0N6v0{6/5+3M6c01682=3E5M5d7h5Y6f3d1 6h286j7i6e5w7r1V5)0g7C6_734_0m0_2S6L0v6K0v0k18776`0;0G0_0Q7Q7F226Q0_5n7e3n7$5D7o0M693d5$7n667w6l5K3%7t296k4Q7?7A3k7D7E4Z7G7I0m7K0M241b7$804^227T047V89783:0k0_2h72816=0_6!7(7R3O6(0S6*0w6,6.2:8s757W8n1%8d0e8D8b1%7Z5A7c8m2v7*7,0e3 4M7*7=4j8S206i7`5J8X8T3I7 8h016r040d1N1Z8I4s83850!7O0R8=5a8d020B0R0x8f2.8a8?047J0w0b7L878|740_7b7$7d8A4r8Q7k4k6b7:7p7y0e4l7^7v9q524l2H7~7 7D8+7H9784997L9a0m1;8z3m958}7U9d6X8p8O96989a7M8`9R8c0_0s9!6{9F859c8r7X790_768g8s8d0V0V9(0;8L5O4p9U9l1|3E4C8U9p7x524C9u8#5Z8Xa38)9B7C9D6|6~70356I0Y6~9`018d939Nah046)6+6-9U5a6Y0Waz6z8@9Hal9K2AaD9S040t8N9-64a58R4Ta4aa7q0e4Ta97;7{8XaTaeaf8+8-0w6u9=9.3:ai1Zak9J1;aoa.8E7S7Uas3K9OaE046}a=71a`8J0;7aaO9jaQ6d8R4/aUa!8$5i4/aZ9w5Kbfa(af9C8s8-2A0R708894a*0b0_0o0Y6Tba5 7gaR9m539oaV9r54bla65K549z6wbqa*7Ia-by8s9Eb36 0YaHa^8;b63N8~900xapb#ajb5bZa/01b99h9 bIa13d5mbLbhab5ic1bP8Wc55kbTbq9Bau9W7L8_7Pb,9P8eb;aF9Xa@aJcj4!8d9%cr4_8L3ib|aP8Pb~0m5x6n2~8Va#c53fc7cIcE7}bUa)bs0_380h9Ma 8+b{9~cA0ga0cDc07mcGa5c85x7s8!c3aW0U7m7Bccbrb_9Ecf862Saparcm9*aGcpcV2Gb04_8GapcxbF6:bHbdbJ5#c2bm8XdhcLbi5x7.c@agcR04bubwap0qbA040D3QcUdc5+0V625,5}5.5`1c0R5;dL2N2I0S1YdI0V5/7d0!0$0(0h04.

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

.128013cPw-7 sSfbgn38k9+]vei;(hN4l,mdo0qp65_:2)=tay1/[ur050E0u0Q0R0v0B0h0g0b0B0R0h0h0P010Q0v0I010406050h0W0D0D0R0X0S040i0F0B0W0=0F0m050U0|0~10120`0I04051i1b1l0U1i0`0E0v0t0*0,0.0:0,0m0l0W0R0l0u0e0I0S0Q0y190g0y0v0l0y0B1N0y0Q0^050#0k0B0u1u0-0/011M1O1Q1O0Q1W1Y1U0Q0X1j1I0*150h0I0R0m0:0N011!1w010j0%0u0m0R0D0u1U1_1{201$231Y26280^0a0g0c0X0F0I0F0h0v180m0g0Z1@0X0X0u0b2t1b2b0m1j0U1I2G1:1=1;1V0E2d1x0v0m252q1U1r1t0+1#2Q2S0m0F2W1U0I2z1j2E2G2-0{1`2u2Y212$0X0 0B1U0R1L2z0j0:030L0L0b2%0u1Q2#0F0e0n0e0T0^0g0T1b0R2.2;0_2:2c2?1$2^2`2|2~0u3001323436382T3b0e1~040g0N3i3k1{3m2E2P013r0R2{1j2}0y2 3133350Z3B2$3D0n3f0n3J2D3l0`3N3p0:3Q3S053U3W3x3Y3A2R3C3c0A3f0A3+1c3-3n2=1v3q0F2_3R3t3V3v3X3z3!3}3$3c0K3f0K432-3.2;3O3=4d3_3y3Z374j3a3c0J3f0J4p453/483;4a3s3T3u3w4x3|393D0f3f0f4G3L4r3o4J3P4L4c4N4e4P3{4i4S3c0o3f0o4X2F4Z472Z4$4b3?3^4f3`4h4z4.0e0q3f0q4?3M4s3:4{4M3@4O4g4y3#4B3d0G0^0T0G584^4t4%4}5f505h4A3D0T3e045z5p465r4|4v4 4Q4-3~3d3F0T3I0U3j3,4Y5E5b4u4)4w4,525L0T3(5B3*5Q3K2F1m2+1b2W2J0E1=2O5b4y2V1s1j2*0u2,3l5S5,4y5 2c0v0E0:332E5y3t6668515i6b0g2h0u6e5w535A3+4I4`0p0^0Z0j613G5U4#0m0j0^2z0b0y0u0X6E0u0L1r6E0F0Q0F0D0v0H0W0u6w6y4`0@040x6V6q2@0^0 0L1Q0h0Q6U443L6W216Y0C6w0g6;3q0^0t3R0u0W0X6#5a4#6Y0O6^6`0:6Y0M6w0`6/5,3N6d01692;3D3F5e7h5Z6g3c1~6i276k7i6f5x7r1U5*0g7C6_6$6{042R6L6J0Z0k17777F0:0F0^0P7O734`6Q0^5o7e3m7!5E7o0L6a3c5%7n677w6m5L3(7t286l4R7;7A3j7D7E7V6%7H0m7J0L231a7!7~4!4`7R047T87783P0k0^2g72896=0^6!7$7P3P6(0R6*0v6,6.2/8q757U8l1$8b0e8B4_217X5B7c8k2u7(7*0e404N7(7:4k8Q1 6j7^5K8V8R3J7}8f6s040d1M1Y8G4t0^7I0v0b7K0u7M0Q8/5b8b020B0Q0w8d2-888H7G8=8@842R8|740^7b7!7d8y4s8O7k4l6c7.7p7y0e4m7?7v9p534m2G7|7}7D8f0m8;828?6J8@0m1:8x3l953O8b939M8f6Y8o9i8C3;9E837L7N8e8q8b0r9c4`9D8183858M3O8A9$7 8D0^0U0U9*8I0v0^5P4q9:9k1{3D4D8S9o7x534D9t8Z5!8Va68%9A7C9C6|6~7034251:6~9|9^8cas9X046)6+6-9:5b6Y0VaB6z9Y9Gao9J2zaF6X0^0s8L8p9ja88P4Ua7ad7q0e4Uac7/7_8VaVahai8)8;6v9?9W8r046}1Yan9Iaq8.a/967Q7S9Q3L9N5Vala@71a|9;9eaQ9V8NaT9l0e4:aWa$8!5j4:a#9v5Lbga*ai9B8q8*2z0Q708694ak9-aIa_aL9ga2bda43c55bhbn8V55bma95LbKbq8(bta-ava;a?6 0XaJa`9Lb18f8~900wbX9,bZ70bX7aba607gbH0m5y5lbLbQ8V5n8X7uaX9qc19y3GbrbU9@aw988^8`bX9Pb.aH99bDb(2Fb24#9(bX8J3hbFaR65b`5y6o2}8Ta%5j5zc27@biaecD6o7Bbra,04370hcm6x8zb9cubb0ga3b{3c5O9nc46n7s8YcHaYc#c7c9caa:9,cd9aby9R9%7ScibBckapbEbzc`048Fb75bcsb@6:b_6e8P5$c$c+c57=c*bMcD7,cLajbV04bvbxbX0p0b0^0z19cR9h600U635-5~5/5{1b0Q5=dH2M2H0R1XdE0U5:7d0Z0#0%0h04.

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

.128013cPw-7 sSfbgn3T8k9+]vei;(h4l,Fmdo0qp65_:2)=tay1/[ur050F0v0R0S0w0B0h0g0b0B0S0h0h0Q010R0w0J010406050h0X0E0E0S0Y0T040i0G0B0X0?0G0m050V0}0 11130{0J04051j1c1m0V1j0{0F0w0u0+0-0/0;0-0m0l0X0S0l0v0e0J0T0R0z1a0g0z0w0l0z0B1O0z0R0_050$0k0B0v1v0.0:011N1P1R1P0R1X1Z1V0R0Y1k1J0+160h0J0S0m0;0O011#1x010j0(0v0m0S0E0v1V1`1|211%241Z27290_0a0g0c0Y0G0J0G0h0w190m0g0!1^0Y0Y0v0b2u1c2c0m1k0V1J2H1;1?1=1W0F2e1y0w0m262r1V1s1u0,1$2R2T0m0G2X1V0J2A1k2F2H2.0|1{2v2Z222%0Y100B1V0S1M2A0j0;030M0M0b2(0v1R2$0G0e0A0e0U0_0g0U1c0S2/2=0`2;2d2@1%2_2{2}2 0v3101333537392U3c0e1 040g0O3j3l1|3n2F2Q013s0S2|1k2~0z303234360!3C2%3E0n3g0n3K2E3m0{3O3q0;3R3T053V3X3y3Z3B2S3D3d0A3g0A3,1d3.3o2?1w3r0G2`3S3u3W3w3Y3A3#3~3%3d0L3g0L442.3/2=3P3?4e3`3z3!384k3b3d0K3g0K4q463:493=4b3t3U3v3x4y3}3a3E0f3g0f4H3M4s3p4K3Q4M4d4O4f4Q3|4j4T3d0p3g0p4Y2G4!482!4%4c3@3_4g3{4i4A4/0e0r3g0r4@3N4t3;4|4N3^4P4h4z3$4C3e0H0_0U0H594_4u4(4~5g515i4B3E0U3f045A5q475s4}4w504R4.3 3e3G0U3J0V3k3-4Z5F5c4v4*4x4-535M0U3)5C3+5R3L4^5V4$5X5f4+5h4S5$415C435+5T5-4J4{5:4 4,525j5z4n5C4p5|455U5 2^5t5I635x540U4E5C4G6a2:1p2,1c2X2K0F1?2P5c4z2W1t1k2+0v2-3m5}1k4z6F2d0w0F0;342F5z3u6M6O645y3d3f0g2i0v6U6i5$1V5|6d3r0_100M1R0h0R0v0M280w0h6H0g5.4{0G0_0Q6{6}2^0k0_0h4b6=0F6H731%0^040y7b6+3=0_6:6=6@0E6_7h5b4$7e0P6H0{6b2G5F6T016P2=3E3G5f7A5!653d1 6Z286#7B6V547F5+7w2:3O7H0M6Q3d5(7G6N7P6%4l0e3)7M296$5@7*7#7T7q6L7%7C1|3E5_7$7/5L7*417-7O7I6W3c6)5S7i010q0_0!0j728a0m0j0_0S0J1{0Y0?260R0M1s0b1K0R0G7o0I0X0v7@4`227e7g7x6K8D6,046.7l8B8H7c0;7e0C8g7r600_0u3S0v0X0Y8C3P7t8U4#4{7e0N7v8%7X7Z0e677~7(7:5k4n837 5#7*8@5+0g936|8h0_2S8t6?0!0k188*8J0;6 04718H958V227o0_5p8H7U6G7W7_7Y7D4D6S9v7)5k4E8}8_809C883H948Q3Q970m990M241b9k9L9h9j2.9l8+747k268%5c8F9%5/6-0S6/6_6=9*8,0_7u9T8a9h0e9e3P9o5C8/8P9u6U8=4V4O7X9B4U206!8~7J0ea53K949Y9f8b0_0d1N1Z9|5W9N9P9b9d9^9m1%9h020B0R0x9W3mai4uar0w0b6?9Rap7s0_8.9r8:9v8=4;a69A8`3E4;9E8554aUagah9K960498aI6?aJ0m1;8O9X9U70aM9=7f9;2^aHaJ8s0v9c0Ra`229h0sb58Ka-b0aLa1aw8R9?b99g0_0V0Vbi019~5Q4raRa39x559zac8656a!7Q5M562H3ka)a*bf9M048Y1Z8#358q0Y8Zbn9Vbn0m9,9.6;a?9tbI7e0Wa}ba9Oa.bOa;2Ab(bg040ta07V4t8;bu5obw9F8 5kb{bAa86X5mbE9JbG9L8ca,8fav9Z8KbL8!0Yb,1;bRccaj9VaD3MaFaqbK8Z8#bn8-b?b!7^bt7{6X5B8^a#5$6Yabb}ad5A9IbGc78ac92A0R8#9Sa@cP0b0_0o0Y8Acx3M7zaSb`7F2~a7aX6X7LcIcF7*5PcMcNc897cbcVbIbVcsbMcha:cjaocl3PayaA0xbU8Xct8$d69(aOc$7ya27P8=5%b|c=b 7,c;bBc?7=bFcNah9Lc bb9ab2auc}cdbj9idba,b*b0d3b.df4$b7bn9~3iaQbeczdlb`7}c,aW9G5z82dsc23e7}92c_cP0_380hbZcp9LcwdVb@dX7`0m66dodtb 8|d*c.3e91dwdx93dza aK2SbSa_dP8WdK9PdNd@2GcqdQ0_9{ei9n0w5ndi8I0gb_cB3e6lcEe25z9De5d%6XeDd.ebd:04cRcTbn0qcX040D3Sd?ex1c6J1n6r0V6t1c0R6ve*2N2I0S1Y6E6s6B7w0!0$0(0h04.

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