Recherche dans une grille triée
On considère un tableau bidimensionnel d'éléments distincts, 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.
Exemple
Cette grille possède bien chaque ligne et chaque colonne triées.
- \(42\) est présente à la ligne 0, colonne 2.
- \(24\) est absent.
Fonctions à utliser
La grille utilisée ici ne sera pas une liste Python et vous n'avez pas un accès direct aux données qu'elle contient.
En revanche, vous avez à votre disposition trois fonctions (déjà chargées en mémoire) telles que :
nb_lignes(grille)renvoie le nombre \(n\) de lignes de la grille.nb_colonnes(grille)renvoie le nombre \(m\) de colonnes de la grille.donne_valeur(grille, i, j)renvoie la valeur degrilleà la ligneiet la colonnej.
On vous demande d'écrire une fonction telle que recherche(cible, grille) renvoie None si la cible est absente de grille, sinon le tuple (i, j) tel que donne_valeur(grille, i, j) est égal à la cible. On définit le coût de la recherche comme le nombre d'appels à la fonction donne_valeur.
On rappelle que la grille possède la propriété que chaque ligne et chaque colonne sont triées.
Attention
Certaines des grilles utilisées dans les tests contiennent beaucoup de valeurs. Une méthode de coût linéaire sera inefficace face à celles-ci.
On limite donc le nombre de lectures dans chaque grille à 2000. Passée cette valeur maximale, tout nouvel accès provoquera une erreur.
Dans les tests, la fonction nb_acces permet de connaitre le nombre de lectures de la grille.
Exemples
Avec la grille définie comme dans le premier test public, on a
>>> recherche(42, grille)
(0, 2)
>>> recherche(24, grille) is None
True
Efficacité
On attend une recherche efficace.
Une écriture itérative pourra être plus simple qu'une écriture récursive. Les deux sont possibles.
Indice
En partant d'un des coins supérieur droit ou inférieur gauche :
- soit on trouve la cible,
- soit on peut éliminer une ligne entière ou une colonne entière
Dans le pire des cas, en \(n+m\) tentatives, on a éliminé toutes les lignes et toutes les colonnes.
Après avoir éliminé une ligne ou une colonne, on se retrouve à chercher une cible dans une grille rectangulaire, ainsi on se retrouve dans une situation similaire à la précédente.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)