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

.128013kg[: r);S/(.lo4y,6b=ac1x5+ud3t28_Pw7evp-fh0*9mnR]is050C0L0E0v0Y0n0Z0f0w0n0v0Z0Z0u010E0Y0N010406050Z0B0U0U0v0g0q040j0o0n0B0@0o0V050k0~1012140|0N04051k1d1n0k1k0|0C0Y0M0,0.0:0=0.0V0c0B0v0c0L0O0N0q0E0Q1b0f0Q0Y0c0Q0n1P0Q0E0`050%0t0n0L1w0/0;011O1Q1S1Q0E1Y1!1W0E0g1l1K0,170Z0N0v0V0=0F011$1y010P0)0L0V0v0U0L1W1{1}221(251!282a0`0a0f0I0g0o0N0o0Z0Y1a0V0f0#1_0g0g0L0w2v1d2d0V1l0k1K2I1=1@1?1X0C2f1z0Y0V272s1W1t1v0-1%2S2U0V0o2Y1W0N2B1l2G2I2/0}1|2w2!232(0g110n1W0v1N2B0P0=030H0H0w2)0L1S2%0o0O0F0O0x0`0f0x1d0v2:2?0{2=2e2^1(2`2|2~300L32013436383a2V3d3d3h0F3k3m1}3o2G2R013t0v2}1l2 0Q313335370#3D2(3F0D3h0D3J2F3n0|3N3r0=3Q3S053U3W3z3Y3C2T3E3e0p3h0p3+1e3-3p2@1x3s0o2{3R3v3V3x3X3B3!3}3$3e0z3h0z432/3.2?3O3=4d3_3A3Z394j3c3e0s3h0s4p453/483;4a3u3T3w3y4x3|3b3F0K3h0K4G3L4r3q4J3P4L4c4N4e4P3{4i4S3e0G3h0G4X2H4Z472#4$4b3?3^4f3`4h4z4.0O0T3h0T4?3M4s3:4{4M3@4O4g4y3#4B3f0R0`0x0R584^4t4%4}5f505h4A3F0x3g045z5p465r4|4v4 4Q4-3~3f205B3I0k3l3,4Y5E5b4u4)4w4,525L0x3(5B3*5Q3K4@5U4#5W5e4*5g4R5#405B425*5S5,4I4`5/4~4+515i5y4m5B4o5{445T5~2_5s5H625w530x4D5B4F694q5-5 6e5X5I5Z643e0x4U5B4W6n3n1o2-1d2Y2L0C1@2Q5b4y2X1u1l2,0L2.6C6a2H054y6S2e0Y0C0=352G5y3v6!6$635x6w212j0L6,6h5#1W5{6c1(0b0`0#0P5|040f6p2_0P0`1=0o0B0M0L0g0H2T1=0B0Z71741(0_040l7j6{3;770v0t7p5a4#7m0r71737q3P0`0c7v4!4`7y7A7k7r040C7G4_237m0h0e710|6U6Y2w6+016%2?3F5N5e7!6u6.3G0f6;6?5?4k3G2I5R7C0J3h0f7}7P3O0Z0C0`02030D0T0i84868885877V7 7+0H6(3e5%7*6#7#6-533(7/296=8n6@7?8k6`7w4`817|7}0W270M0o0Y1#0.0f0M3R0L0B0g2x8J89877f0g7h0f2t0E0B1#271=8J0L0+2T1t0w8*0f0c0f0$2x8e7X5E8g8i0O5^8l7;5K7?408r2a905!926_7_8z238B727}2x1}0+8K1S0Z0E1#1Y0f790f7U7X7W2;3N8{7%4l6*8m7,534m948t9C5L663+7C9d9f9N0f9o7b0g0Y258)0+370V1t2v0+2y0n8T0i0L0y7c0w0Y8.7z9t8f9B8h9y0O6k8 8u7=5j4D9F966v9_997Y80829e9O8:8=0E2x8Y1bac0#0+0U0B0n0@0N1!9#1#0D0m8^9v4s9x1}4T9Aa17-4Ua09|915j6y9K9b1(9M9f9(aN8c0iat6C9w9?8|4:4N8g8v5j4:aD9H7?aW3J9N7L016}049T7K7C0V7Ea;aJ0=0o0`0u0ua^7H2_6~7 5b7m9s6o8_aT6,8|55aX9?aZ3F55a$8o5Lbca*a97Ba_a-0`2B8!0g1c7Xbob03s7s7ub8bp7m0db35.a@bCby0=7m0XaR3L8`aU9^5nazaE975jbTbibf6w5l7^3obJ7ZbRax6w5A9{a%bX3gbZ9}5yb.5*a+7Ca.390Z0LbG7I0`b645b)0faw0V5y7)2 aYb@6w20b?aFcaa4bnbx7Qbz042(0U0t2B0H0#0H1=0^1!0E7ibwa,a{04a~cC7C7m7oc65Vb2cHbpcE0Oa cn7M7FcL7x0`0hc123cE0k0kc!1(0U0Y0`5)b7au6Zb+c96w8kccbece3f8q7:bVa25$ckbna,a?a/9Y9.c0cObK01cEcG2/cm4tbIdfcD0`0AcS3Oc+c-c)a`0`0Sdr01cJdvd5cqcs0LcudCcxan0$cBc:cTdc0`c%dvdp045PdJ3O7SbO6Vb98n8|0x8~c_aA6i93c~b:5y8~b`d3b|0`a:dadKd51YdvbEdyd;d78.d`0`bNd?3Oddde3ndgcM04d_cWc204bFecb1d68-d9dj7CcEdme35bdP3jeg7le1dnb4c3dVa5c865bUd+6w9Ed*bj7?0x9Jd.cl7~d:04bs8Pbvelbpd^2p7a7c7e0V7gdIaSbD0`cKdSe9ebe,cX049:eUdbd58,d8ew4#ene{4`dPc.e(db7JepbH7Ne004cZ9;c6eB6w9`d$c 7-6j6:8sd%5#9`eM9Oa,b}0*ekf2dKb5ezbQbabSaHfgeE3faCeHb!fFd2eNe84#a.eRbue~eh78eY7d8V7hf8e+fvdhea7tf8e=e7d4dif!exe;fRcoe_d etbLcYfy0k6X6D6R6F6O1d0E6Ig12O2J7t1!2I6G7W0#0%0)0Z04.