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

.128013fd*6nmi74=]3y_ 9pu08ts5[/v1b(P)l;gow-ahR:+rxS2cek,.050c0W0v0M0h0G0w0p0V0G0M0w0w0k010v0h0r010406050w0s0g0g0M0R0n040T0J0G0s0@0J0f050z0~1012140|0r04051k1d1n0z1k0|0c0h0A0,0.0:0=0.0f0I0s0M0I0W0L0r0n0v0N1b0p0N0h0I0N0G1P0N0v0`050%0C0G0W1w0/0;011O1Q1S1Q0v1Y1!1W0v0R1l1K0,170w0r0M0f0=0U011$1y010b0)0W0f0M0g0W1W1{1}221(251!282a0`0a0p0E0R0J0r0J0w0h1a0f0p0#1_0R0R0W0V2v1d2d0f1l0z1K2I1=1@1?1X0c2f1z0h0f272s1W1t1v0-1%2S2U0f0J2Y1W0r2B1l2G2I2/0}1|2w2!232(0R110G1W0M1N2B0b0=030o0o0V2)0W1S2%0J0L0U0L0B0`0p0B1d0M2:2?0{2=2e2^1(2`2|2~300W32013436383a2V3d3d3h0U3k3m1}3o2G2R013t0M2}1l2 0N313335370#3D2(3F0m3h0m3J2F3n0|3N3r0=3Q3S053U3W3z3Y3C2T3E3e0j3h0j3+1e3-3p2@1x3s0J2{3R3v3V3x3X3B3!3}3$3e0x3h0x432/3.2?3O3=4d3_3A3Z394j3c3e0e3h0e4p453/483;4a3u3T3w3y4x3|3b3F0i3h0i4G3L4r3q4J3P4L4c4N4e4P3{4i4S3e0u3h0u4X2H4Z472#4$4b3?3^4f3`4h4z4.0L0q3h0q4?3M4s3:4{4M3@4O4g4y3#4B3f0t0`0B0t584^4t4%4}5f505h4A3F0B3g045z5p465r4|4v4 4Q4-3~3f205B3I0z3l3,4Y5E5b4u4)4w4,525L0B3(5B3*5Q3K4@5U4#5W5e4*5g4R5#405B425*5S5,4I4`5/4~4+515i5y4m5B4o5{445T5~2_5s5H625w530B4D5B4F694q5-5 6e5X5I5Z643e0B4U5B4W6n3n1o2-1d2Y2L0c1@2Q5b4y2X1u1l2,0W2.6C6a2H054y6S2e0h0c0=352G5y3v6!6$635x6w212j0W6,6h5#1W5{6c1(0X0`0#0b5|6Y4_230K3h716p2_0b0`1=0J0s0A0W0R0o2T1=0s0w776{0=0_040D7n5a5.7b0M0C7t4!4`7q0Y710p783s0`0I7z731(7C7E7G3;6~7K3O7q0F0P710|6U720p6+016%2?3F5N5e7$6u6.3G0p6;6?5?4k3G2I5R7o0175040p807F7Z7P010w0c0`02030m0q0H898b8d8a8c7X7S7-0o6(3e5%7,6#7%6-533(7;296=8s6@7^8p6`7u4`863h810O270A0J0h1#0.0p0A3R0W0s0R2x8O8e8c7j0R7l0p2t0v0s1#271=8O0W0+2T1t0V8/0p0I0p0$2x8j833N8l8n0L5^8q7?5K7^408w2a955!976_7{8E238G7 810c1}0+8P1S0w0v1#1Y0p7d0p7W7Z7Y2;8 8r7(1}3F66948z7@5j4m998y7.539G8D7A9h879j81819t7f0R0h258.0+370f1t2v0+2y0G8Y0H0W0S7g0V0h8?7D9y8k9C8m7)4C6*9~8A5j4D9M9b6v0L6k3+7|9i9W9W8_8{2Q0w1b0v8W0+0g0s0G0@0r1!9-1#0m0Z8}9A4s90a00L6y9H9O5L4Ua79I965jaF9R7L0=ae819:aU8h0Haz6C9B6,914:4N8la43F4:aKaH7^a%3J9W846}049#7O7|0f7Ia`9g1(0J0`0k0ka~9S7H040c7S5b7q9x6o8~aB9~9155a(a39J3F55a-8t5Lbja;af80a?0`2B8)0R1c7Z7Fa{7w7ybfb67p0`0yba7v047JbHaQ017q0laY3L5EaC9E6w5lbka87/5n6:8xb%6ib#3J9zaZbga#aD5za2b,5#3gbpa*6w5Abtbv7|a@390w0WbM7B0`bd45bQ7#bhb@7+2 a)bm6w20b}ck5M9e9Vaf84a|042(0g0C2B0o0#0o1=0^1!0v7mbC84b104b4cI7|7q7scd5V7RcNa 0=cK0Lb5bRcubPaAbIbS0`0Fc823cK0z0zc,1(0g0h0`5)bec%2wbY0f5y8pciblaMc b*9aaL9c5j5$cqbuc2cV3P0`8;9_c7cUc(cKcM2/bDdec#cZ3OcK0Qds5bc?c^c;cW0`0ddAc)7rdEcucwcy0WcAdLcDat0$cHc{dt0`c/dEdy045PdSbbc*bV6Va!8s910B93d1b`7^d,d59Nbqd:935*dcdpc(a@a_dkc!bFdE7qbLcRbNdh8?e30`bUe0dTcLdn3nd|e1041Yea04e5d!e79*didw4#duet4`dX3je6c904ecdo84bcd%7!c}65b_d7a90B9L7=eMb(9Q3ld{a=c3bx0$8UbBeEbEek2p7e7g7i0f7kdRb;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;0z6X6D6R6F6O1d0v6Igc2O2J7x1!2I6G7Y0#0%0)0w04.