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 degrille;nb_colonnes(grille)renvoie le nombre \(n\) de colonnes degrille;valeur(grille, i, j)renvoie la valeur degrillesituée à l'intersection de la ligneiet de la colonnej.
É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}
\]
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
.128013 ,:çkn9àSvsuO8;y7e62×-0wr5_pag)R1IiN/ûé=mhb.4x+jodt c(P3qlf 050X0r0Y0C0I0)0k0Z0!0)0C0k0k0N010Y0I0B010406050k0l0O0O0C0y0p040i0W0)0l0~0W0f0Z020C0O0B0o0Z0F0r180y0(0l0r0k050K1517191b130B041z1G051J0K1J1L1G130X0I0j0?0^0`0|0P0I0D0P0)1Z0P0Y11050.0Q0)0r1U0_0{011Y1!1$1!0Y1,1.1*0Y0Q0W0X1b1+0y1H0Y0P0?1e0k0B0C0f0|0t011:1W010*0:0r0f1m0r1*2b2d2i1=2l1.2o0O2q040a0Z0$0y0W0B0W0k0I1h1j0,290y0y0r0!2L1z2s0f1H0K272X0Y2524260X2u0|1$0f2n2I1*1R1T0@1;2+0I2-0f211S1*0B2Q1H2V2X32142c1j2?2j2{0y180)110Z0G2U3612352t381=3a3c3e0t3h2d3j2V2*013o0C3d040Z0%3s2W133v3m0|3y3A0Z0S3E3u363w3K3e0z3O3G3Q3I3x0W3b3z3e0s3V3k371V3n3!3p3B0q3)3H3,3J3.3$3B0n3=3X3@3Z3#3L0g3}3l3 3S040G0w443+2@403/0G3g1A3i3W454d470G3r4i3t4k4c393_3A0G3D4q3F3*3R4v110G3N4z2X2 0r2X2;2!0X2(3w0!212A0+1S1H4J313i3O054R0,4Y4l2j0e110,0*4!3?4d0x3e4/3~4m0*112Q0!0P0r0y4}0r4@4)1=10040#534t3n110!0I1-524H4B3Y560b3O0Z5i46110D0y0:1.593w560E0c3V0Z5B5n4:39110O5m5o4d0W110N5I5E5b040f0Q0A1_2-1y5h5P0|56585Y4^5F045r5t5g345Z015x5A5C5J5)0f5O5(1=5L045N4H5D5{3J115S0A4R0)1i5W5v5j115$5.623x5q5s0)5u5%545!110E5=5B5@5Q0I5`6n015}5 32616x0O0I114a4H065C6C5a63040V6w6M6y5M6Q3R646U3Y5}0v6X3 6E4E6r6L3w4+040x1Y6l6B6t6o576b5p046v606=6S04020)0Y0o6A3i6*3Y0f5G6#5K116!6|5/6%486^4d5;7e6g0W4=042d0X7a2j5#7i5)6P7l6x5}020D72743t766$6F046H6f6x5x5z6I6K6K6}78040j3z7s5|6T7y6R7T7V1.0l0y7v556d7+6N5+6k5-4Z5/5k7X6N6{7L6R7^7!6V6O7.5:6p6)7R5/6,0I4.7 77117%7_6~7B728f7T5d5f82567O326J7Q8s7S117x6;5/6z8j8v8f6Z8f7g4h8q8s6s87110r1$8a8x6g7$7W8b3 7A710o8A048l6:7?6g8o858I8u6`8C7Z8P6x7T7{756}5}0U8E7I8G4j8I7G4d6,8M0k7=3t6}8(7P8~5?8K042Q0Y7)5_8T7j7-6m7#118=957@115l9h7w8n84988J6g6,9d9f8f0e0!110J1i944A0K4$4K1I301z4M1z0Y4O9R2$2Y20222!0C5f4L4V1F4(6R2Q0O0A0*0C0e0r0A0P0%111r1t1v1x0Z8p4Z1M3j1G0m1j0C7)0/0Y0Z0B0l0b0Z2N9.0d1i0Z2d3z0W0D1wac0M0!5s2Q0Z0l2-0Z0*1i2S0Iah1v0I29172n0!1/2c0yai0!0!0M0,aK0h0Z0^0Z7%0r7)0Z2J9e0M1/a5292_0Z2_0*0M5saWaK0Da5510R1Ia1040H0)0Z0r0T0I0k0YaI1f2Ja/0=3z0D3!2K0P2z0=2HaXau1/7:1.ad1/6}19bb18b20T11090#0O096q605V9|0-8 2jbo27bqa~bt0#0fbx5m67691xac0X1ia8ahbS0favbk4R0La8142#1i0D040X2d0=bk0B0Ias0,0=0!0_2Ub(0fb*9}a^131e3j1$041r51504~a}0T0Pa5b11S1/b,0fb@cb9{0?0_0rbRbTaS1/b!a81xb$5/bFbc0CbrbJ0O0ubLby32a@0Kc313c3c54~c7cf0I4}0W0Y0W6Eck15aK4}0CckbAadcpbZ0Wb#a}b1a}0f0jb;ahbn5sbGczbI04bubw680DbK0EbM4HcHcJ05cL2RcN51adcQ0PcScU0IcWaXcZckbObXcfc(crc*ctc-2nc:2F1jc?bpc_bsc{bK09c~bvd1cF3id40Ic2dKcM4 da0r0*2lb^aHco0fa8c)c+cubD1=cxbHdAc|0UcE3OdJ3j0Kc1130K0,0.0:0k04.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(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
.128013 ,:çkn9àSvsuO8;y7e62×-0wr5_pag)R1Ii/ûé=mhb.4x+jodt c(P3qlf 050W0r0X0C0I0(0k0Y0Z0(0C0k0k0M010X0I0B010406050k0l0N0N0C0y0p040i0V0(0l0}0V0f0Y020C0N0B0o0Y0F0r170y0%0l0r0k050J1416181a120B041y1F051I0J1I1K1F120W0I0j0=0@0_0{0O0I0D0O0(1Y0O0X10050-0P0(0r1T0^0`011X1Z1#1Z0X1+1-1)0X0P0V0W1a1*0y1G0X0O0=1d0k0B0C0f0{0t011/1V010)0/0r0f1l0r1)2a2c2h1;2k1-2n0N2p040a0Y0#0y0V0B0V0k0I1g1i0+280y0y0r0Z2K1y2r0f1G0J262W0X2423250W2t0{1#0f2m2H1)1Q1S0?1:2*0I2,0f201R1)0B2P1G2U2W31132b1i2=2i2`0y170(100Y0G2T3511342s371;393b3d0t3g2c3i2U2)013n0C3c040Y0$3r2V123u3l0{3x3z0Y0R3D3t353v3J3d0z3N3F3P3H3w0V3a3y3d0s3U3j361U3m3Z3o3A0q3(3G3+3I3-3#3A0n3;3W3?3Y3!3K0g3|3k3~3R040G0w433*2?3 3.0G3f1z3h3V444c460G3q4h3s4j4b383^3z0G3C4p2V1H2 1y2:2Z0W2%3v0Z202z0*1R1G2~0r303h3N054I0+4Q4k2i0e100+0)4S3=4c0x3d4%3}4l0)102P0Z0O0r0y4=0r4,4X1;0 040!4{4s3m100Z0I1,4`4y4W520{4~0b3N0Y3)3Q100D0y0/1-513v4~0E0c3U0Y5u5g4(4Y4!0r4$595h3X4*3A5o3X0f4/044;4?4^4?0A4;0l0y2I0j58335x4}10505C5Y3I100I5H3~5d5f5D45100U5+4c5q5s59065v5|5w4-5y040I5B315~4|5(615.5%010V10020(0X0o0M695 53040N6j666b100v6o5b010N0I104g645/4c0V5F2c0W6t5i045=59656u6c04020D6g6i6L6B2i6w10495$6k5c105_315{5}6+6V6l0j3y6H3X6O6T6A6a0f106/1-5S5?2i4~5#5X6#3w5j5l0(5n6!6p5-6U6_5)6 5Z045e7d746`6J7g6$040E5t6+5}6-0{4Z61633h6M6I6|6;3~6?6@7A7v750455577o014~6(4i7t7T7B3X7x2P0X5S0f7E5@5!7O7m5*7a6u7c6^7l5;7O5q7s7U7V3~7x0r1#7z3s7_4l6{6:7k6p6O6e6g7$38545679737b6%7@7^5v7J7X0,7!896l5M4@4_5Q2Q5S5U5W4R6a717)7f846N100T8o0{6X477=107j7/6p7m6K8e7-107r5`8i80607|0k8x7 7J7Q5f6*8X5u8k4:8m0y7#8D6I8q5O0r8t0Z8v1R8$4z8z7(7,6I7+8S5p8M8H7K8R7I6a6O6s8?3X8J6z8y747?8W8j7e6m996?997m0f0P0A1^2,1x933X8A9B5:045k5m8 5a977q8h7J9u9r107H8%9p9v0A4I0(1h9z8L4 8B9G778d9k8f9M9n8-6a8l7Z8;9t8/4_8_8{8}5V9#729+6u8J6Z969C989g9F8=a47F6r7O9i9#8V6)1y4U4P4Aak0J4D1y0X4Fap2#2X1 212Z0C572W4D1E9K3X2P0N0A0)0C0e8`0O0$101q1s1u1w0Y7R3s1H3i1F0m1i0C5S0.0X0Y0B0l0b0Y2MaI0d1h0Y2c3y0V0D1va,0L0Z5l2P0Y0l2,0Y0)1h2R0Ia;1u0I28162m0Z1.2b0ya=0Z0Z0L0+bh0h0Y0@0Y6|0r5S0Y2I7Z0L1.a#282^0Y2^0)0L5lbtbh0Da#4_0QaWaC0H0(0Y0r0S0I0k0Xbf1e2IbI0;3y0D3Z2J0O2y0;2Gbub11.9H781.2M7J18b*17bX0S10090!0N09ag7A9yaS0,8Y1;b`26b|bTb 0!0fc35f9X9Z1wa,0W1ha(a;co0fb21-280Ka(132!1h0D040W2c0;cv0B0Ia 0+0;0Z0^2TcA0fcCaTbO051d3i1#041q9_4_bS0S0Oa#bW8~a-cF0=c)aR0=0^0rcncpbp1.4IcxbSbWc90{cbb+0Cb}cf0N0uchc43sbN0JcY12cYc!5Nc$1Q4=0V0X0V6wc;14bh4=0Cc;c6a-c_cvc|a(1wdB0f0jcJa;b_5lccd4ce04c0c29Y0Dcg0Eci59dcde05dg2Qdi4?a-0Idldndp1vbvbudtc;ckctb@dyc{0Vc}dCbSdEdG1idIb{dLb~dNcg09dQc1dTda2VdW0IcXeddh8rd$5A2kcNbec^0fa(dzd_dBc e0dKd5e40N0Td93Nec3i0JcW12an0,0.0:04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)