Intrus dans une liste

On considère des tableaux de nombres dont tous les éléments sont présents exactement trois fois à la suite, sauf un élément qui est présent une unique fois et que l'on appelle « l'intrus ». Voici quelques exemples :

Exemple

Python
tab_a = [3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8, 5, 5, 5]
#l'intrus est 7

tab_b = [8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3]
#l'intrus est 8

tab_c = [5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8]
#l'intrus est 3

On remarque qu'avec de tels tableaux :

  • pour les indices multiples de 3 situĂ©s strictement avant l'intrus, l'Ă©lĂ©ment correspondant et son voisin de droite sont Ă©gaux,
  • pour les indices multiples de 3 situĂ©s après l'intrus, l'Ă©lĂ©ment correspondant et son voisin de droite - s'il existe - sont diffĂ©rents.

Ce que l'on peut observer ci-dessous en observant les valeurs des paires de voisins marquées par des caractères ^ :

Text Only
[3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8, 5, 5, 5]
 ^  ^     ^  ^     ^  ^     ^  ^     ^  ^     ^  ^     ^  ^     ^
 0        3        6        9        12       15       18       21

Dans des listes comme celles ci-dessus, un algorithme récursif pour trouver l'intrus consiste alors à choisir un indice i multiple de 3 situé approximativement au milieu des indices parmi lesquels se trouve l'intrus.

Puis, en fonction des valeurs de l'élément d'indice i et de son voisin de droite, à appliquer récursivement l'algorithme à la moitié droite ou à la moitié gauche des indices parmi lesquels se trouve l'intrus.

Par exemple, si on s’intéresse à l’indice 12, on voit les valeurs 2 et 4 qui sont différentes : l’intrus est donc à gauche de l’indice 12 (indice 12 compris)

En revanche, si on s’intéresse à l’indice 3, on voit les valeurs 9 et 9 qui sont identiques : l’intrus est donc à droite des indices 3-4-5, donc à partir de l’indice 6.

Compléter la fonction récursive trouver_intrus qui met en œuvre cet algorithme

###(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

.128013b];=wlSd[f-:*431(gnahR.p/+uerovm)6 x72i,y9c8s_Ptk05050i0C0W0u0N0g0T0J0R0g0u0T0T0e010W0N0y010406050T0B0G0G0u0D0P040h0E0g0B0@0E0t050z0~1012140|0y04051k1d1n0z1k0|0i0N0F0,0.0:0=0.0t0s0B0u0s0C0l0y0P0W0v1b0J0v0N0s0v0g1P0v0W0`050%0b0g0C1w0/0;011O1Q1S1Q0W1Y1!1W0W0D1l1K0,170T0y0u0t0=0M011$1y010k0)0C0t0u0G0C1W1{1}221(251!282a0`0a0J0V0D0E0y0E0T0N1a0t0J0#1_0D0D0C0R2v1d2d0t1l0z1K2I1=1@1?1X0i2f1z0N0t272s1W1t1v0-1%2S2U0t0E2Y1W0y2B1l2G2I2/0}1|2w2!232(0D110g1W0u1N2B0k0=030U0U0R2)0C1S2%0E0l0M0l0q0`0J0q1d0u2:2?0{2=2e2^1(2`2|2~300C32013436383a2V3d3d3h0M3k3m1}3o2G2R013t0u2}1l2 0v313335370#3D2(3F0p3h0p3J2F3n0|3N3r0=3Q3S053U3W3z3Y3C2T3E3e0o3h0o3+1e3-3p2@1x3s0E2{3R3v3V3x3X3B3!3}3$3e0Z3h0Z432/3.2?3O3=4d3_3A3Z394j3c3e0I3h0I4p453/483;4a3u3T3w3y4x3|3b3F0L3h0L4G3L4r3q4J3P4L4c4N4e4P3{4i4S3e0S3h0S4X2H4Z472#4$4b3?3^4f3`4h4z4.0l0Q3h0Q4?3M4s3:4{4M3@4O4g4y3#4B3f0Y0`0q0Y584^4t4%4}5f505h4A3F0q3g045z5p465r4|4v4 4Q4-3~3f205B3I0z3l3,4Y5E5b4u4)4w4,525L0q3(5B3*5Q3K4@5U4#5W5e4*5g4R5#405B425*5S5,4I4`5/4~4+515i5y4m5B4o5{445T5~2_5s5H625w530q4D5B4F694q5-5 6e5X5I5Z643e0q4U5B4W6n3n1o2-1d2Y2L0i1@2Q5b4y2X1u1l2,0C2.6C6a2H054y6S2e0N0i0=352G5y3v6!6$635x6w212j0C6,6h5#1W5{6c1(0X0`0#0k5|6Y4_230f3h716p2_0k0`1=0E0B0F0C0D0U2T1=0B0T776{0=0_040r7n5a5.7b0u0b7t4!4`7q0O710J783s0`0s7z731(7C7E7G3;6~7K3O7q0H0m710|6U720J6+016%2?3F5N5e7$6u6.3G0J6;6?5?4k3G2I5R7o0175040J807F7Z7P010T0i0`02030p0Q0d898b8d8a8c7X7S7-0U6(3e5%7,6#7%6-533(7;296=8s6@7^8p6`7u4`863h810w270F0E0N1#0.0J0F3R0C0B0D2x8O8e8c7j0D7l0J2t0W0B1#271=8O0C0+2T1t0R8/0J0s0J0$2x8j833N8l8n0l5^8q7?5K7^408w2a955!976_7{8E238G7 810i1}0+8P1S0T0W1#1Y0J7d0J7W7Z7Y2;8 8r7(1}3F66948z7@5j4m998y7.539G8D7A9h879j81819t7f0D0N258.0+370t1t2v0+2y0g8Y0d0C0K7g0R0N8?7D9y8k9C8m7)4C6*9~8A5j4D9M9b6v0l6k3+7|9i9W9W8_8{2Q0T1b0W8W0+0G0B0g0@0y1!9-1#0p0x8}9A4s90a00l6y9H9O5L4Ua79I965jaF9R7L0=ae819:aU8h0daz6C9B6,914:4N8la43F4:aKaH7^a%3J9W846}049#7O7|0t7Ia`9g1(0E0`0e0ea~9S7H040i7S5b7q9x6o8~aB9~9155a(a39J3F55a-8t5Lbja;af80a?0`2B8)0D1c7Z7Fa{7w7ybfb67p0`0jba7v047JbHaQ017q0caY3L5EaC9E6w5lbka87/5n6:8xb%6ib#3J9zaZbga#aD5za2b,5#3gbpa*6w5Abtbv7|a@390T0CbM7B0`bd45bQ7#bhb@7+2 a)bm6w20b}ck5M9e9Vaf84a|042(0G0b2B0U0#0U1=0^1!0W7mbC84b104b4cI7|7q7scd5V7RcNa 0=cK0lb5bRcubPaAbIbS0`0Hc823cK0z0zc,1(0G0N0`5)bec%2wbY0t5y8pciblaMc b*9aaL9c5j5$cqbuc2cV3P0`8;9_c7cUc(cKcM2/bDdec#cZ3OcK0Ads5bc?c^c;cW0`0ndAc)7rdEcucwcy0CcAdLcDat0$cHc{dt0`c/dEdy045PdSbbc*bV6Va!8s910q93d1b`7^d,d59Nbqd:935*dcdpc(a@a_dkc!bFdE7qbLcRbNdh8?e30`bUe0dTcLdn3nd|e1041Yea04e5d!e79*didw4#duet4`dX3je6c904ecdo84bcd%7!c}65b_d7a90q9L7=eMb(9Q3ld{a=c3bx0$8UbBeEbEek2p7e7g7i0t7kdRb;c(cPdHe2eA237NedcSa^ere9e{eu0`dvf0exc@04c_e:bRe`e$dqcTepeBc+9|cdeJ6wabd.eR6ia6eQa.d9abd`dcbw04c5djffe_caeHbXcfbZ3faFfnfs5yaJfrd@d9aOeUeVddd}eYbze#ehct7be)9Ze,e.emcQfBb7ele^7M0`9{fcc(drf/bJ04f=fZe%e8fAf97Td$fi2;0z6X6D6R6F6O1d0W6Igc2O2J7x1!2I6G7Y0#0%0)0T04.