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

🐍 Script 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 ^ :

📋 Texte

[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

Évaluations restantes : 5/5

.128013f06S:d=4-yr./oxpg2mcb1w937Rve[ l,8*+P5)ti]kn;ua(_sh050g0D0O0V0P0G0Y0F0u0G0V0Y0Y0h010O0P0q010406050Y0U0t0t0V0l0k040e0o0G0U0@0o0S050n0~1012140|0q04051k1d1n0n1k0|0g0P0C0,0.0:0=0Z0P0r0Z0G1B0Z0O0`050%0v0G0D1w0/0;011A1C1E1C0O1K1M1I0O0l1l0O0Z0,170Y0q0V0S0=0s011O1y010b0)0D0S0V0t0D1I1+1-1=1Q1^1M1{1}0`0a0F0L0l0o0q0o0Y0P1a0S0F0#1)0l0l0D0u2i1d200S1l0n1%2v1!1$1#1J0g220=1E0S1`2f1I1t1v0-1P2F0P2H0S0o2L1I0q2o1l2t2v2Z0}1,2j2N1?2S0l110G0`0F0w2s2%0{2$212)1Q2+2-2/0s2=1-2@2t2E012|0V2.040F0z302u0|332`0=36380F0i3c322%343i2/0M3m3e3o3g350o2,372/0d3t2^2(1x2{3y2}390A3D3f3G3h3I3A390I3M3v3O3x3z3j0y3U2_3W3q040w0c3#3F2O3X3J0w2;1e2?3u3$3.3(0w2 3?313^3-2*3Q380w3b3~3d3E3p430`0w3l473n3_423Y4c3s4f404a4j3)3C4m493w3{3L4f1o2X1d2L2y0g1$2D3w0u2T1~1l4B1m4z2#4x4H0#2Y3V3.0R0`0#0b3m4t3W0x2/4Z3N3`0b0`1!0o0U0C0D0l0X2Q1!0U0Y4(4T1?0_040W4{4h2{4,0V0v51411Q4~0H3m0F4!3`0`0r57345a5c5e2*4W5i3w4~0N0f3,344$390F5y5p3W0Y0g0`02030z0y0T5F5H5J5G5I5u3w5C2/5y0F0B1`0C0o0P1N0.0F0C370D0U0l2k5!5K5I4@0l4_0F2g0O0U1N1`1!5!0D0+2Q1t0u5~0F0r0F0$2k5P5B5D5x5y0g1-0+5#1E0Y0O1N1K0F4.0F5t4s4)1?5R6c5T5y6m4:0l0P1^5}0+4H0S1t2i0+2l0G5.0T0D0p4;0u0P625b6r4|1Q6u6w6w65672D0Y1b0O5,0+0t0U0G0@0q1M6J1N0z0m693.6Y5T6M6~5N0T3t6w5m1Q4V046B5l6s53045h4f5d7a0=0o0`0h0h796W3h5o4x7g014~6q2Z066Z5T740=762o5^0l1c7e7z3554567q7n7s0`0E5A5f7c7Q4}0`0Q3t7w7y7r760D0*0D7T590`7u3@7x5z7r0S0`2S0t0v2o0X0#0X1!0^1M0O4`7G7r7i047l827M4~507L527o040g7m8c01840j8g588d7d2#7r5r7)7h0`0n0n8s010t0P0`467v7.7f7M7;776G6S7(878h84862Z8F8h8H8o2?8R8m8i0`0K8l348z8B8x840J8x898x8H7?7^0D7`8=7}6;0$818p7M848v8x8%043}8|8h8r4m8E7H76788M8X8H1K8,7O8.0`608K9g047W9c348O8P8V7H9e559m7P8b9d9j8J628#3w848!9p3w913=948X4~9o8Q7H7t728E7Z7M7B0$5*7F9Q7:4,2c4/4;4?0S4^8{2?9R0`8a9M3p7J9m6U9#8G9B618L9{8N8Z9E3W918C9/8q0`9`9t9$8e9m0N9T7x990`7$0Y9 a7887+ag9Uai047C9Za37R4-9)4=5:4_9m9=an8S9^9z5ja9aw5n7SaI5qaK9I3%9}9laO3W967v1d4Q0D2v2Wa#4A1u4C2y2B2w551M2v4B0|0n0#0%0)0Y04.