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

.1280137*w4xh)1(+5-,_s3u:/S[ bn=ve08im.tP]R69p2drgylckfao050P0B0H0X0E0T0p0w0U0T0X0p0p0z010H0E0N010406050p0r0F0F0X0Q0S040u0Y0T0r0?0Y0y050t0}0 11130{0N04051j1c1m0t1j0{0P0E0A0+0-0/0;0-0y0R0r0X0R0B0m0N0S0H0g1a0w0g0E0R0g0T1O0g0H0_050$0x0T0B1v0.0:011N1P1R1P0H1X1Z1V0H0Q1k1J0+160p0N0X0y0;0O011#1x010W0(0B0y0X0F0B1V1`1|211%241Z27290_0a0w0I0Q0Y0N0Y0p0E190y0w0!1^0Q0Q0B0U2u1c2c0y1k0t1J2H1;1?1=1W0P2e1y0E0y262r1V1s1u0,1$2R2T0y0Y2X1V0N2A1k2F2H2.0|1{2v2Z222%0Q100T1V0X1M2A0W0;030o0o0U2(0B1R2$0Y0m0O0m0i0_0w0i1c0X2/2=0`2;2d2@1%2_2{2}2 0B3101333537392U3c3c3g0O3j3l1|3n2F2Q013s0X2|1k2~0g303234360!3C2%3E0q3g0q3I2E3m0{3M3q0;3P3R053T3V3y3X3B2S3D3d0e3g0e3*1d3,3o2?1w3r0Y2`3Q3u3U3w3W3A3Z3|3#3d0l3g0l422.3-2=3N3;4c3^3z3Y384i3b3d0L3g0L4o443.473:493t3S3v3x4w3{3a3E0b3g0b4F3K4q3p4I3O4K4b4M4d4O3`4h4R3d0D3g0D4W2G4Y462!4#4a3=3@4e3_4g4y4-0m0M3g0M4=3L4r3/4`4L3?4N4f4x3!4A3e0C0_0i0C574@4s4$4|5e4 5g4z3E0i3f045y5o455q4{4u4~4P4,3}3e1 5A3H0t3k3+4X5D5a4t4(4v4+515K0i3%5A3)5P3J4?5T4!5V5d4)5f4Q5!3 5A415)5R5+4H4_5.4}4*505h5x4l5A4n5`435S5}2^5r5G615v520i4C5A4E684p5,5~6d5W5H5Y633d0i4T5A4V6m3m1n2,1c2X2K0P1?2P5a4x2W1t1k2+0B2-6B692G054x6R2d0E0P0;342F5x3u6Z6#625w6v202i0B6+6g5!1V5`6b1%0V0_0!0W5{6X4^220d3g706o2^0W0_1;0Y0r0A0B0Q0o2S1;0r0p766`0;0^040j7m595-7a0X0x7s4Z4_7p0n700w773r0_0R7y721%7B7D7F3:6}7J3N7p0h0s700{6T710w6*016$2=3E5M5d7#6t6-3F0w6:6=5=4j3F2H5Q7n0174040w7 7E7Y7O010p0P0_00887W7R7,0o6%3d5$7+6!7$6,523%7:286;8j6?7@8g6_7t4_853g800K260A0Y0E1!0-0w0A3Q0B0r0Q2w8F007i0Q7k0w2s0H0r1!261;8F0B0*2S1s0U8#0w0R0w0#2w8a823M8c8e0m5@8h7=5J7@3 8n298{5Z8}6^7`8v228x7~800P1|0*8G1R0p0H1!1X0w7c0w7V7Y7X2:8=8i7%1|3E658`8q7?5i4l8 8p7-529w8u7z97869980809j7e0Q0E248!0*360y1s2u0*2x0T000B0f7f0U0E8)7C9o8b9s8d7(4B6)9:8r5i4C9C916u0m6j3*7{989M9M8,8.2P0p1a0H8N0*0F0r0T0?0N1Z9Z1!0q0G8:9q4r8?9=0m6x9x9E5K4T9|9y8|5iau9H7K0;a3808800ao6B9r6+8@4/4M8c9_3E4/azaw7@aQ3I9M836|049R7N7{0y7Ha*961%0Y0_0z0za.9I7G040P7R5a7p9n6n8;aq9:8@54aR9^9z3E54aW8k5Kb6a!a47 a$0_2A8V0Q1b7Y7Ea+7v7xb2a_7o0_0va}7u047IbuaF017p0JaL3K5Dar9u6v5kb79}7.5m6/8obQ6hbO3I9paMb3aOas5y9@bV5!3fbcaT6v5zbgbi7{a%380p0Bbz7A0_b044bD7!b4b%7*2~aSb96v1 b-c75L949La483a,042%0F0x2A0o0!0o1;0@1Z0H7lbp83a;04a@cv7{7p7rc05U7QcAa/0;cx0ma^bEchbCapbvbF0_0hb{22cx0t0tcV1%0F0E0_5(b1cQ2vbL0y5x8gc5b8aBc/bT90aA925i5#cdbhb=cI3O0_8%9+b`cHcRcxcz2.bqd1cOcM3Ncx0kdf5ac$c(c!cJ0_0cdncS7qdrchcjcl0Bcndycqai0#cuc+dg0_cYdrdl045OdFa~cTbI6UaN8j8@0i8_c;b*7@dVc^9DbddZ8_5)c dccRa%a)d7cNbsdr7pbycEbAd48)d?0_bHd:dGcyda3md,d;041Xd}04d^dNd`9Wd5dj4!dheg4_dK3id_b|04d db83a dQ7Zc-64b)c`9~0i9B7;ezbR9G3kd+a#b?bk0#8Lboerbre72o7d7f7h0y7jdEb!cRcCdud=en227Me0cFa(eed|e+eh0_die:ekc%04c)eZbEe*ePddcGeceocU9.c0ew6va0dXeE6h9{eDaXc|a0d*c bj04b^d6f2e)b}eubKc2bM3eaufaff5xayfed%c|aDeHeId0d-eLbmeOe4cg7aeS9PeVeXe9cDfoa`e8e(7L0_9-e cRdefYbw04f#fMeQd{fne|7SdPf52:0t6W6C6Q6E6N1c0H6Hf 2N2I7w1Z2H6F7X0!0$0(0p04.