Recherche dans une grille triée

On considère un tableau bidimensionnel d'entiers positifs, dont chaque ligne et chaque colonne est triée dans l'ordre croissant. On souhaite savoir si un élément cible est présent dans ce tableau.

Dans cette grille, chaque ligne et chaque colonne est triée.

\[ \begin{matrix} 11 & 33 & \mathbf{42} & 63 \\ 20 & 52 & 67 & 80 \\ 25 & 61 & 88 & 95 \\ \end{matrix} \]

Les lignes et les colonnes sont numérotées à partir du rang \(0\).

  • \(42\) est présent à la ligne \(0\), colonne \(2\).
  • \(24\) est absent.
Accès aux valeurs

Le tableau bidimensionnel grille utilisé ici n'est pas une liste Python et vous n'avez pas un accès direct aux données qu'il contient.

En revanche, vous avez à votre disposition trois fonctions nb_lignes, nb_colonnes, valeur (déjà chargées en mémoire) telles que :

  • nb_lignes(grille) renvoie le nombre \(m\) de lignes de grille ;
  • nb_colonnes(grille) renvoie le nombre \(n\) de colonnes de grille ;
  • valeur(grille, i, j) renvoie la valeur de grille située à l'intersection de la ligne i et de la colonne j.

Écrire une fonction recherche qui prend en paramètres un élément cible et une grille grille. Cette grille possède la propriété que chaque ligne et chaque colonne est triée.

Si l'élément cible est absent de grille alors la fonction renvoie None.

Sinon la fonction renvoie le tuple (i, j) tel que valeur(grille, i, j) soit égale à cible.

Attention

Si on teste toutes les valeurs d'une grille avec \(m\) lignes et \(n\) colonnes, on devra lire dans le pire des cas \(m \times n\) valeurs.

On demande d'écrire un programme plus efficace lisant dans le pire des cas \(m + n - 1\) valeurs. Le non respect de cette consigne provoquera une erreur.

Dans les tests, la fonction nb_acces, déjà chargée en mémoire, permet de connaître le nombre de lectures de la grille.

Exemples

Avec la grille définie comme dans le premier test, on a :

>>> recherche(42, grille)
(0, 2)
>>> recherche(24, grille) is None
True
Indice

On peut commencer par lire la valeur se trouvant au coin supérieur droit de la grille. Pour la grille de l'exemple, on pourrait écrire un algorithme qui :

  • pour la recherche de \(88\) ne lise que successivement \(63\) - \(80\) - \(95\) - \(88\) ;
  • pour la recherche de \(52\) ne lise que successivement \(63\) - \(42\) - \(67\) - \(52\) ;
  • pour la recherche de \(30\) ne lise que successivement \(63\) - \(42\) - \(33\) - \(11\) - \(20\) - \(25\)
\[ \begin{matrix} 11 & 33 & 42 & 63 \\ 20 & 52 & 67 & 80 \\ 25 & 61 & 88 & 95 \\ \end{matrix} \]

###(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 : 10/10

.128013s3_8ufvIy n7aSû1me(P24:jtwiçh)6Oo;bcdg/0làqp.r-,=+Nk95R×xé050L0s0z0n0B0P0b0k0K0P0n0b0b0X010z0B0S010406050b0f0r0r0n0U0j040o0H0P0f0~0H0l0k020n0r0S0I0k0%0s180U0R0f0s0b050N1517191b130S041z1G051J0N1J1L1G130L0B0h0?0^0`0|0D0B0M0D0P1Z0D0z11050.0J0P0s1U0_0{011Y1!1$1!0z1,1.1*0z0J0H0L1b1+0U1H0z0D0?1e0b0S0n0l0|0v011:1W010g0:0s0l1m0s1*2b2d2i1=2l1.2o0r2q040a0k0u0U0H0S0H0b0B1h1j0,290U0U0s0K2L1z2s0l1H0N272X0z2524260L2u0|1$0l2n2I1*1R1T0@1;2+0B2-0l211S1*0S2Q1H2V2X32142c1j2?2j2{0U180P110k0q2U3612352t381=3a3c3e0v3h2d3j2V2*013o0n3d040k0c3s2W133v3m0|3y3A0k0w3E3u363w3K3e0$3O3G3Q3I3x0H3b3z3e0F3V3k371V3n3!3p3B0m3)3H3,3J3.3$3B0e3=3X3@3Z3#3L0#3}3l3 3S040q0O443+2@403/0q3g1A3i3W454d470q3r4i3t4k4c393_3A0q3D4q3F3*3R4v110q3N4z2X2 0s2X2;2!0L2(3w0K212A0+1S1H4J313i3O054R0,4Y4l2j0!110,0g4!3?4d0A3e4/3~4m0g112Q0K0D0s0U4}0s4@4)1=10040t534t3n110K0B1-524H4B3Y560W3O0k5i46110M0U0:1.593w560E0x3V0k5B5n4:39110r5m5o4d0H110X5I5E5b040l0J0d1_2-1y5h5P0|56585Y4^5F045r5t5g345Z015x5A5C5J5)0l5O5(1=5L045N4H5D5{3J115S0d4R0P1i5W5v5j115$5.623x5q5s0P5u5%545!110E5=5B5@5Q0B5`6n015}5 32616x0r0B114a4H065C6C5a63040y6w6M6y5M6Q3R646U3Y5}0V6X3 6E4E6r6L3w4+040A1Y6l6B6t6o576b5p046v606=6S04020P0z0I6A3i6*3Y0l5G6#5K116!6|5/6%486^4d5;7e6g0H4=042d0L7a2j5#7i5)6P7l6x5}020M72743t766$6F046H6f6x5x5z6I6K6K6}78040h3z7s5|6T7y6R7T7V1.0f0U7v556d7+6N5+6k5-4Z5/5k7X6N6{7L6R7^7!6V6O7.5:6p6)7R5/6,0B4.7 77117%7_6~7B728f7T5d5f82567O326J7Q8s7S117x6;5/6z8j8v8f6Z8f7g4h8q8s6s87110s1$8a8x6g7$7W8b3 7A710I8A048l6:7?6g8o858I8u6`8C7Z8P6x7T7{756}5}0Y8E7I8G4j8I7G4d6,8M0b7=3t6}8(7P8~5?8K042Q0z7)5_8T7j7-6m7#118=957@115l9h7w8n84988J6g6,9d9f8f0!0K110Z1i944A0N4$4K1I301z4M1z0z4O9R2$2Y20222!0n5f4L4V1F4(6R2Q0r0d0g0n0!0s0d0D0c111r1t1v1x0k8p4Z1M3j1G0G1j0n7)0/0z0k0S0f0W0k2N9.0C1i0k2d3z0H0M1wac0*0K5s2Q0k0f2-0k0g1i2S0Bah1v0B29172n0K1/2c0Uai0K0K0*0,aK0Q0k0^0k7%0s7)0k2J9e0*1/a5292_0k2_0g0*5saWaK0Ma5510T1Ia1040i0P0k0s0)0B0b0zaI1f2Ja/0=3z0M3!2K0D2z0=2HaXau1/7:1.ad1/6}19bb18b20)11090t0r096q605V9|0-8 2jbo27bqa~bt0t0lbx5m67691xac0L1ia8ahbS0lavbk4R0pa8142#1i0M040L2d0=bk0S0Bas0,0=0K0_2Ub(0lb*9}a^131e3j1$041r51504~a}0)0Da5b11S1/b,0lb@cb9{0?0_0sbRbTaS1/b!a81xb$5/bFbc0nbrbJ0r0(bLby32a@0Nc313c3c54~c7cf0B4}0H0z0H6Eck15aK4}0nckbAadcpbZ0Hb#a}b1a}0l0hb;ahbn5sbGczbI04bubw680MbK0EbM4HcHcJ05cL2RcN51adcQ0DcScU0BcWaXcZckbObXcfc(crc*ctc-2nc:2F1jc?bpc_bsc{bK09c~bvd1cF3id40Bc2dKcM4 da0s0g2lb^aHco0la8c)c+cubD1=cxbHdAc|0YcE3OdJ3j0Nc1130N0,0.0:0b04.

###(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 : 10/10

.128013s3_8ufvIy n7aSû1me(P24:jtwiçh)6Oo;bcdg/0làqp.r-,=+k95R×xé050L0s0z0n0B0P0b0k0K0P0n0b0b0X010z0B0S010406050b0f0r0r0n0U0j040o0H0P0f0}0H0l0k020n0r0S0I0k0$0s170U0R0f0s0b050N1416181a120S041y1F051I0N1I1K1F120L0B0h0=0@0_0{0D0B0M0D0P1Y0D0z10050-0J0P0s1T0^0`011X1Z1#1Z0z1+1-1)0z0J0H0L1a1*0U1G0z0D0=1d0b0S0n0l0{0v011/1V010g0/0s0l1l0s1)2a2c2h1;2k1-2n0r2p040a0k0u0U0H0S0H0b0B1g1i0+280U0U0s0K2K1y2r0l1G0N262W0z2423250L2t0{1#0l2m2H1)1Q1S0?1:2*0B2,0l201R1)0S2P1G2U2W31132b1i2=2i2`0U170P100k0q2T3511342s371;393b3d0v3g2c3i2U2)013n0n3c040k0c3r2V123u3l0{3x3z0k0w3D3t353v3J3d0#3N3F3P3H3w0H3a3y3d0F3U3j361U3m3Z3o3A0m3(3G3+3I3-3#3A0e3;3W3?3Y3!3K0!3|3k3~3R040q0O433*2?3 3.0q3f1z3h3V444c460q3q4h3s4j4b383^3z0q3C4p2V1H2 1y2:2Z0L2%3v0K202z0*1R1G2~0s303h3N054I0+4Q4k2i0Z100+0g4S3=4c0A3d4%3}4l0g102P0K0D0s0U4=0s4,4X1;0 040t4{4s3m100K0B1,4`4y4W520{4~0W3N0k3)3Q100M0U0/1-513v4~0E0x3U0k5u5g4(4Y4!0s4$595h3X4*3A5o3X0l4/044;4?4^4?0d4;0f0U2I0h58335x4}10505C5Y3I100B5H3~5d5f5D45100y5+4c5q5s59065v5|5w4-5y040B5B315~4|5(615.5%010H10020P0z0I0X695 53040r6j666b100V6o5b010r0B104g645/4c0H5F2c0L6t5i045=59656u6c04020M6g6i6L6B2i6w10495$6k5c105_315{5}6+6V6l0h3y6H3X6O6T6A6a0l106/1-5S5?2i4~5#5X6#3w5j5l0P5n6!6p5-6U6_5)6 5Z045e7d746`6J7g6$040E5t6+5}6-0{4Z61633h6M6I6|6;3~6?6@7A7v750455577o014~6(4i7t7T7B3X7x2P0z5S0l7E5@5!7O7m5*7a6u7c6^7l5;7O5q7s7U7V3~7x0s1#7z3s7_4l6{6:7k6p6O6e6g7$38545679737b6%7@7^5v7J7X0,7!896l5M4@4_5Q2Q5S5U5W4R6a717)7f846N100Y8o0{6X477=107j7/6p7m6K8e7-107r5`8i80607|0b8x7 7J7Q5f6*8X5u8k4:8m0U7#8D6I8q5O0s8t0K8v1R8$4z8z7(7,6I7+8S5p8M8H7K8R7I6a6O6s8?3X8J6z8y747?8W8j7e6m996?997m0l0J0d1^2,1x933X8A9B5:045k5m8 5a977q8h7J9u9r107H8%9p9v0d4I0P1h9z8L4 8B9G778d9k8f9M9n8-6a8l7Z8;9t8/4_8_8{8}5V9#729+6u8J6Z969C989g9F8=a47F6r7O9i9#8V6)1y4U4P4Aak0N4D1y0z4Fap2#2X1 212Z0n572W4D1E9K3X2P0r0d0g0n0Z8`0D0c101q1s1u1w0k7R3s1H3i1F0G1i0n5S0.0z0k0S0f0W0k2MaI0C1h0k2c3y0H0M1va,0)0K5l2P0k0f2,0k0g1h2R0Ba;1u0B28162m0K1.2b0Ua=0K0K0)0+bh0Q0k0@0k6|0s5S0k2I7Z0)1.a#282^0k2^0g0)5lbtbh0Ma#4_0TaWaC0i0P0k0s0(0B0b0zbf1e2IbI0;3y0M3Z2J0D2y0;2Gbub11.9H781.2M7J18b*17bX0(10090t0r09ag7A9yaS0,8Y1;b`26b|bTb 0t0lc35f9X9Z1wa,0L1ha(a;co0lb21-280pa(132!1h0M040L2c0;cv0S0Ba 0+0;0K0^2TcA0lcCaTbO051d3i1#041q9_4_bS0(0Da#bW8~a-cF0=c)aR0=0^0scncpbp1.4IcxbSbWc90{cbb+0nb}cf0r0%chc43sbN0NcY12cYc!5Nc$1Q4=0H0z0H6wc;14bh4=0nc;c6a-c_cvc|a(1wdB0l0hcJa;b_5lccd4ce04c0c29Y0Mcg0Eci59dcde05dg2Qdi4?a-0Bdldndp1vbvbudtc;ckctb@dyc{0Hc}dCbSdEdG1idIb{dLb~dNcg09dQc1dTda2VdW0BcXeddh8rd$5A2kcNbec^0la(dzd_dBc e0dKd5e40r0Yd93Nec3i0NcW12an0,0.0:04.