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

.128013l(9 _4:;=vm26-uS8w.Rs*3/]+fr7gebh[pPic05a,onkyd1x)t050V0F0Z0P0L0b0v0e0M0b0P0v0v0j010Z0L0J010406050v0p0l0l0P0C0U040q0R0b0p0@0R0S050y0~1012140|0J04051k1d1n0y1k0|0V0L0k0,0.0:0=0.0S0E0p0P0E0F0o0J0U0Z0H1b0e0H0L0E0H0b1P0H0Z0`050%0G0b0F1w0/0;011O1Q1S1Q0Z1Y1!1W0Z0C1l1K0,170v0J0P0S0=0m011$1y010B0)0F0S0P0l0F1W1{1}221(251!282a0`0a0e0K0C0R0J0R0v0L1a0S0e0#1_0C0C0F0M2v1d2d0S1l0y1K2I1=1@1?1X0V2f1z0L0S272s1W1t1v0-1%2S2U0S0R2Y1W0J2B1l2G2I2/0}1|2w2!232(0C110b1W0P1N2B0B0=030f0f0M2)0F1S2%0R0o0m0o0W0`0e0W1d0P2:2?0{2=2e2^1(2`2|2~300F32013436383a2V3d3d3h0m3k3m1}3o2G2R013t0P2}1l2 0H313335370#3D2(3F0x3h0x3J2F3n0|3N3r0=3Q3S053U3W3z3Y3C2T3E3e0g3h0g3+1e3-3p2@1x3s0R2{3R3v3V3x3X3B3!3}3$3e0O3h0O432/3.2?3O3=4d3_3A3Z394j3c3e0n3h0n4p453/483;4a3u3T3w3y4x3|3b3F0D3h0D4G3L4r3q4J3P4L4c4N4e4P3{4i4S3e0r3h0r4X2H4Z472#4$4b3?3^4f3`4h4z4.0o0d3h0d4?3M4s3:4{4M3@4O4g4y3#4B3f0N0`0W0N584^4t4%4}5f505h4A3F0W3g045z5p465r4|4v4 4Q4-3~3f205B3I0y3l3,4Y5E5b4u4)4w4,525L0W3(5B3*5Q3K4@5U4#5W5e4*5g4R5#405B425*5S5,4I4`5/4~4+515i5y4m5B4o5{445T5~2_5s5H625w530W4D5B4F694q5-5 6e5X5I5Z643e0W4U5B4W6n3n1o2-1d2Y2L0V1@2Q5b4y2X1u1l2,0F2.6C6a2H054y6S2e0L0V0=352G5y3v6!6$635x6w212j0F6,6h5#1W5{6c1(0T0`0#0B5|6Y4_230s3h716p2_0B0`1=0R0p0k0F0C0f2T1=0p0v776{0=0_040c7n5a5.7b0P0G7t4!4`7q0Q710e783s0`0E7z731(7C7E7G3;6~7K3O7q0Y0h710|6U720e6+016%2?3F5N5e7$6u6.3G0e6;6?5?4k3G2I5R7o0175040e807F7Z7P010v0V0`02030x0d0i898b8d8a8c7X7S7-0f6(3e5%7,6#7%6-533(7;296=8s6@7^8p6`7u4`863h810u270k0R0L1#0.0e0k3R0F0p0C2x8O8e8c7j0C7l0e2t0Z0p1#271=8O0F0+2T1t0M8/0e0E0e0$2x8j833N8l8n0o5^8q7?5K7^408w2a955!976_7{8E238G7 810V1}0+8P1S0v0Z1#1Y0e7d0e7W7Z7Y2;8 8r7(1}3F66948z7@5j4m998y7.539G8D7A9h879j81819t7f0C0L258.0+370S1t2v0+2y0b8Y0i0F0X7g0M0L8?7D9y8k9C8m7)4C6*9~8A5j4D9M9b6v0o6k3+7|9i9W9W8_8{2Q0v1b0Z8W0+0l0p0b0@0J1!9-1#0x0t8}9A4s90a00o6y9H9O5L4Ua79I965jaF9R7L0=ae819:aU8h0iaz6C9B6,914:4N8la43F4:aKaH7^a%3J9W846}049#7O7|0S7Ia`9g1(0R0`0j0ja~9S7H040V7S5b7q9x6o8~aB9~9155a(a39J3F55a-8t5Lbja;af80a?0`2B8)0C1c7Z7Fa{7w7ybfb67p0`0Iba7v047JbHaQ017q0zaY3L5EaC9E6w5lbka87/5n6:8xb%6ib#3J9zaZbga#aD5za2b,5#3gbpa*6w5Abtbv7|a@390v0FbM7B0`bd45bQ7#bhb@7+2 a)bm6w20b}ck5M9e9Vaf84a|042(0l0G2B0f0#0f1=0^1!0Z7mbC84b104b4cI7|7q7scd5V7RcNa 0=cK0ob5bRcubPaAbIbS0`0Yc823cK0y0yc,1(0l0L0`5)bec%2wbY0S5y8pciblaMc b*9aaL9c5j5$cqbuc2cV3P0`8;9_c7cUc(cKcM2/bDdec#cZ3OcK0Ads5bc?c^c;cW0`0wdAc)7rdEcucwcy0FcAdLcDat0$cHc{dt0`c/dEdy045PdSbbc*bV6Va!8s910W93d1b`7^d,d59Nbqd:935*dcdpc(a@a_dkc!bFdE7qbLcRbNdh8?e30`bUe0dTcLdn3nd|e1041Yea04e5d!e79*didw4#duet4`dX3je6c904ecdo84bcd%7!c}65b_d7a90W9L7=eMb(9Q3ld{a=c3bx0$8UbBeEbEek2p7e7g7i0S7kdRb;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;0y6X6D6R6F6O1d0Z6Igc2O2J7x1!2I6G7Y0#0%0)0v04.