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

.128013s3_8èufvy n7aêS1me(P24:jtwi][h)6Oo;bcdg/T0làqp!.rL-,=+k95Ré050M0s0z0n0B0R0b0k0L0R0n0b0b0#010z0B0U010406050b0g0r0r0n0X0j040p0I0R0g0 0I0l0k020n0r0U0J0k0*0s190X0T0g0s0b050O16181a1c140U041A1H051K0O1K1M1H140M0B0i0@0_0{0}0E0B0N0E0R1!0E0z12050/0K0R0s1V0`0|011Z1#1%1#0z1-1/1+0z0K0I0M1c1,0X1I0z0E0@1f0b0U0n0l0}0v011;1X010h0;0s0l1n0s1+2c2e2j1?2m1/2p0r2r040a0k0u0X0I0U0I0b0B1i1k0-2a0X0X0s0L2M1A2t0l1I0O282Y0z2625270M2v0}1%0l2o2J1+1S1U0^1=2,0B2.0l221T1+0U2R1I2W2Y33152d1k2@2k2|0X190R120k0q2V3713362u391?3b3d3f0v3i2e3k2W2+013p0n3e040k0c3t2X143w3n0}3z3B0k0w3F3v373x3L3f0)3P3H3R3J3y0I3c3A3f0G3W3l381W3o3#3q3C0m3*3I3-3K3/3%3C0e3?3Y3^3!3$3M0(3~3m403T040q0Q453,2^413:0q3h1B3j3X464e480q3s4j3u1J311A2=2#0M2)3x0L222B0,1T1I300s323j3P054B0-4J4m2k0%120-0h4L3@4e0A3f4W3 4n0h12190l1w2e0z4#4Q1?11040t4/4d3a121}0s0n0g4^3x4=0F0x3W0k560k3+3S4T0s0K1h3P584X2k0I120#5f593Z0r0B124b4r3G575g4$4`042m0l5m5h1?5j045l5t3C5n470K122y503Z4=4@5I5K4n4{0n1.4}4 5T5D0}525C5x5E120Z5)4:0}5p124i3306065v5U4R120A1Z1/5.4_3o5b5d4.5I5w5/015F020R0z0J5H3368623K125A5P404=545I5_5v575{63045p1%0s5!6h6v0}5F6g3j6i51125S355$3y645e676D6a120$615a5z2`6n4e5(6R6N5F0O0O6W5o5q044q5@6t6u6N4S040B4V6%5*6k044|4~6!2k4=0D726w6y0B6A765%120C6,406F6G3u6I3Z0l4)0;796B4K6N6p556=6t6S7m040-657f4e6F7C5y787a6|695F6V7J6j015;497u6=6S6^0s1%6{6C6N7y707q4s7s12755#6}6O6x7o7I7Z7-5F5-7N3x7Q5?7r7-4=7e7_3Z5F0V7i2X7k477n6z7%866S7@7F1?7{7b017t6r7v7w7!6l6Z817g5k8f6~7H8b5J6(5,8u7P6.7|3u6s7T6@127W0b0s8i8k6;8m6?7-6^2R0z0g0X5B8r5V7/8a3*0O4N4I4t8*0O4w1A0z4y8/2%2Z21232#5X1/2Y4w1G4P7O2R0r0d0h0n0%0s0d0E0c121s1u1w1y0k6q351N3k1H0H1k1h7o8L0k0g2.0k2R0L0E0s0X9x1:1S9x0I0z0I5p9f0k0K0`0+1:160X0k0R000I0K8L0X0i0n2M0k161T4-1:0x9R9g9Y1/8W0?0M0g0k7$9#2L0g9N0?0n9Y0l0z9R0n0k9-6A9Q4*4,9 9O1ja00+0N3A9g0S9+8W0k2I2K9!0M2e0?1/9?8{5Z0k0t9.9Q2`9D0s0F0!0@7W1/0?am9`9g0n300faHab0k1S0h0h0+2Ra90b0W1J9l040Ya2a4aja70g9(0k1ya00:0l2Ka1ak920B0f2Ra3afaj9;as5Y4~aQ6`aTaV0z9Caa1kaz0B0L0saY9k8 0Y000+2|0l0L0+0kae0X4-2La?300+8Lbm9C009t9s0l0B9J2|0r0Ka{a*4-0W0k9na-0ba00M1j0LaE0X0/2`0k9J0_9K0I0g0^1:302`0L10afa|9#1:b73c2`9za-a00r0o2AbZ1xa?4B0l1S9!4M4C3x1^1$1(1*903x6^5~2n8B7y7A6Q7=7K126c6e858y7-7y6m7,698O4K8(4C3Ca.9?b%0yb%0X0?0iaU6`0B9NbMbO2I8WbrbtbSbm2aa;2$0g0Ba{9S3A0N3#2L0Eb~4~9Ga~bA9u0X0+0U0+0 9!az0+5A79b 0Bb;9?9z5p2.br9R3#0bb!a%a}a62ea8b70ka2c_bo2$b%cKbebN9o0 1%9ra:a=bBc62O3Zc91`1)2s8S5}5 8M8Z4R0L120P0X1x4LcA4O9haZ1R1Tc81(dCcc6S2x2o2q122D0p0L0X10a00u0j281j4L4H90344K8)cd3Z6^4U8i4Z5Jcw7O0l4(6xdfa+9 8N6K8i7#at71e46J04537S878!ck66cm7O7EdJ8g6.5s8P567x8p8Yer3xeteD7l5M045Oei5QedeL886 eg8x6S6$eG8s047^eV4e8h6r8Gen5|04cg60eu0}0%dL04dNdPeO6#129i6He(1?0L0q12039vc@c_2L0B1j0k0y0gda0g00ahbdb 1:b#a(de4+eadh0b0Ibtdm0gdoem5`8o8#7p8BeF6HeTeN6Mct6PeqfB8z047MeZ5ycvfEcx120Ffz126*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.