Nombre manquant⚓︎

Soit $n$ un nombre entier supérieur ou égal à $2$. On se donne un tableau contenant tous les entiers entre $0$ et $n$ sauf un nombre qui a été supprimé. Ce tableau est trié dans l'ordre croissant.

Le nombre supprimé n'est ni $0$ ni $n$.

Par exemple, pour $n=5$, on peut prendre [0, 1, 2, 4, 5]. Tous les entiers entre $0$ et $5$ sont présents sauf le $3$.

Écrire la fonction manquant qui prend en paramètre un tel tableau et renvoie la valeur manquante.

Attention

Certains des tableaux utilisés dans les tests sont très grands. Une méthode de coût linéaire sera inefficace face à ceux-ci.

On limite donc le nombre de lectures dans chaque tableau à 500. Passé cette valeur maximale, tout nouvel accès provoquera une erreur.

Exemples

>>> manquant([0, 2])
1
>>> manquant([0, 1, 3])
2
>>> manquant([0, 1, 2, 4, 5])
3
>>> manquant([0, 1, 2, 3, 4, 6])
5

Évaluations restantes : 10/10

.128013:Lp(40ed3; 1jo5_ên)h]6,qc[y!uvà8i2+ms7=wlSatf-9ORrg.TéPkbè/050i0h0S0R0H0P0L0l0z0P0R0L0L0N010S0H0d010406050L0D0K0K0R0Y0B040Q0o0P0D0 0o0s0l020R0K0d0k0l0X0h190Y0y0D0h0L050+16181a1c140d041A1H051K0+1K1M1H140i0H0E0@0_0{0}0u0H0Z0u0P1!0u0S12050/0)0P0h1V0`0|011Z1#1%1#0S1-1/1+0S0)0o0i1c1,0Y1I0S0u0@1f0L0d0R0s0}0I011;1X010T0;0h0s1n0h1+2c2e2j1?2m1/2p0K2r040a0l0%0Y0o0d0o0L0H1i1k0-2a0Y0Y0h0z2M1A2t0s1I0+282Y0S2625270i2v0}1%0s2o2J1+1S1U0^1=2,0H2.0s221T1+0d2R1I2W2Y33152d1k2@2k2|0Y190P120l0m2V3713362u391?3b3d3f0I3i2e3k2W2+013p0R3e040l0j3t2X143w3n0}3z3B0l0f3F3v373x3L3f0p3P3H3R3J3y0o3c3A3f0w3W3l381W3o3#3q3C0M3*3I3-3K3/3%3C0G3?3Y3^3!3$3M0V3~3m403T040m0g453,2^413:0m3h1B3j3X464e480m3s4j3u1J311A2=2#0i2)3x0z222B0,1T1I300h323j3P054B0-4J4m2k0(120-0T4L3@4e0O3f4W3 4n0T12190s1w2e0S4#4Q1?11040e4/4d3a121}0h0R0D4^3x4=0t0b3W0l560l3+3S4T0h0)1h3P584X2k0o120N5f593Z0K0H124b4r3G575g4$4`042m0s5m5h1?5j045l5t3C5n470)122y503Z4=4@5I5K4n4{0R1.4}4 5T5D0}525C5x5E120U5)4:0}5p124i3306065v5U4R120O1Z1/5.4_3o5b5d4.5I5w5/015F020P0S0k5H3368623K125A5P404=545I5_5v575{63045p1%0h5!6h6v0}5F6g3j6i51125S355$3y645e676D6a120J615a5z2`6n4e5(6R6N5F0+0+6W5o5q044q5@6t6u6N4S040H4V6%5*6k044|4~6!2k4=0A726w6y0H6A765%120v6,406F6G3u6I3Z0s4)0;796B4K6N6p556=6t6S7m040-657f4e6F7C5y787a6|695F6V7J6j015;497u6=6S6^0h1%6{6C6N7y707q4s7s12755#6}6O6x7o7I7Z7-5F5-7N3x7Q5?7r7-4=7e7_3Z5F0C7i2X7k477n6z7%866S7@7F1?7{7b017t6r7v7w7!6l6Z817g5k8f6~7H8b5J6(5,8u7P6.7|3u6s7T6@127W0L0h8i8k6;8m6?7-6^2R0S0D0Y5B8r5V7/8a3*0+4N4I4t8*0+4w1A0S4y8/2%2Z21232#5X1/2Y4w1G4P7O2R0K0q0T0R0(0h0q0u0j121s1u1w1y0l6q351N3k1H0W1k1h7o8L0l0D2.0l2R0z0u0h0Y9x1:1S9x0o0S0o5p9f0l0)0`0$1:160Y0l0P000o0)8L0Y0E0R2M0l161T4-1:0b9R9g9Y1/8W0?0i0D0l7$9#2L0D9N0?0R9Y0s0S9R0R0l9-6A9Q4*4,9 9O1ja00$0Z3A9g0F9+8W0l2I2K9!0i2e0?1/9?8{5Z0l0e9.9Q2`9D0h0t0x0@7W1/0?am9`9g0R300*aHab0l1S0T0T0$2Ra90L0!1J9l040ca2a4aja70D9(0l1ya00:0s2Ka1ak920H0*2Ra3afaj9;as5Y4~aQ6`aTaV0S9Caa1kaz0H0z0haY9k8 0c000$2|0s0z0$0lae0Y4-2La?300$8Lbm9C009t9s0s0H9J2|0K0)a{a*4-0!0l9na-0La00i1j0zaE0Y0/2`0l9J0_9K0o0D0^1:302`0z10afa|9#1:b73c2`9za-a00K0r2AbZ1xa?4B0s1S9!4M4C3x1^1$1(1*903x6^5~2n8B7y7A6Q7=7K126c6e858y7-7y6m7,698O4K8(4C3Ca.9?b%0nb%0Y0?0EaU6`0H9NbMbO2I8WbrbtbSbm2aa;2$0D0Ha{9S3A0Z3#2L0ub~4~9Ga~bA9u0Y0$0d0$0 9!az0$5A79b 0Hb;9?9z5p2.br9R3#0Lb!a%a}a62ea8b70la2c_bo2$b%cKbebN9o0 1%9ra:a=bBc62O3Zc91`1)2s8S5}5 8M8Z4R0z120#0Y1x4LcA4O9haZ1R1Tc81(dCcc6S2x2o2q122D0Q0z0Y10a00%0B281j4L4H90344K8)cd3Z6^4U8i4Z5Jcw7O0s4(6xdfa+9 8N6K8i7#at71e46J04537S878!ck66cm7O7EdJ8g6.5s8P567x8p8Yer3xeteD7l5M045Oei5QedeL886 eg8x6S6$eG8s047^eV4e8h6r8Gen5|04cg60eu0}0(dL04dNdPeO6#129i6He(1?0z0m12039vc@c_2L0H1j0l0n0Dda0D00ahbdb 1:b#a(de4+eadh0L0obtdm0Ddoem5`8o8#7p8BeF6HeTeN6Mct6PeqfB8z047MeZ5ycvfEcx120tfz126*8B7Q6:4k8m7U126`ci5Wb1eS7)047+fPe589fye@737dfT5Gcre|8v7:f+7~e_fu7veA7z5cclfI7?8te-7.8wf_fLg869e#ey8ndF047Wf%gbeff*ecf-eef;7;gges8Agbgi7}fQ0480fM5+0484f(fxgw7j8dgzgG5:8Dgse`8F8Q8R69cu8qgQ6T5GgKgdgb8egAgS8lg38Igm0=dIf/ejgU5ugWf|018T0.8WeCgx6Xg)5@1Ad|8+8}4F148-0.0:0=04.

Aide (1)

Le tableau peut être partagé en deux zones : les valeurs situées avant la valeur manquante et celles situées après.

Aide (2)

Une recherche dichotomique est plus efficace qu'une approche linéaire. Les valeurs situées avant la valeur manquante sont égales à leur position dans le tableau (leur indice), celles situées après sont différentes.

Aide (3)

La valeur manquante est la première valeur du tableau différente de son indice.