Aller au contenu

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ée.

\[ \begin{matrix} 11 & 33 & \mathbf{42} & 63 \\ 20 & 52 & 67 & 80 \\ 25 & 61 & 88 & 95 \\ \end{matrix} \]
  • \(42\) est présente à la ligne 0, colonne 2.
  • \(24\) est absent.

La grille ne sera pas donnée, mais vous avez à votre disposition trois fonctions telles que :

  1. nb_lignes(grille) renvoie le nombre \(n\) de lignes de la grille.
  2. nb_colonnes(grille) renvoie le nombre \(m\) de colonnes de la grille.
  3. donne_valeur(grille, i, j) renvoie la valeur de grille à la ligne i et la colonne j.
  4. grille ne sera pas une liste Python et vous n'avez aucun autre accès aux données.

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 cout 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 est triée.

Il existe plusieurs algorithmes pour une grille de \(n\) lignes et \(m\) colonnes, dont on donne le cout dans le pire des cas est :

  1. Recherche exhaustive dans chaque case, dont le cout est \(n×m\).
  2. Recherche dichotomique sur chaque ligne dont le cout est environ \(n\log(m)\).
  3. Recherche dichotomique sur chaque colonne dont le cout est environ \(m\log(n)\).
  4. Recherche efficace, dont le cout est \(m+n\).

On attend une recherche efficace. Une écriture itérative pourra être plus simple qu'une écriture récursive. Les deux sont possibles.

Exemples

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

🐍 Console Python
>>> # script exécuté
>>> recherche(42, grille)
(0, 2)
>>> recherche(24, grille) is None
True
###
# testsbksl-nlbksl-nl# Pour ce test public grille est une liste Python,bksl-nl# mais ce ne sera pas toujours le cas !bksl-nlbksl-nlgrille = [bksl-nl [11, 33, 42, 63],bksl-nl [20, 52, 67, 80],bksl-nl [25, 61, 88, 95],bksl-nl]bksl-nlbksl-nlbksl-nldef nbpy-undlignes(grille):bksl-nl return len(grille)bksl-nlbksl-nlbksl-nldef nbpy-undcolonnes(grille):bksl-nl return len(grille[0])bksl-nlbksl-nlbksl-nldef donnepy-undvaleur(grille, i, j):bksl-nl global coutbksl-nl assert 0 <= i < 3bksl-nl assert 0 <= j < 4bksl-nl cout += 1bksl-nl return grille[i][j]bksl-nlbksl-nlbksl-nlcout = 0bksl-nlresultat = recherche(42, grille)bksl-nlassert cout <= 7, "Trop de tentatives"bksl-nlassert resultat == (0, 2), "Mauvaises coordonnées"bksl-nlbksl-nlcout = 0bksl-nlresultat = recherche(24, grille)bksl-nlassert cout <= 7, "Trop de tentatives"bksl-nlassert resultat is None, "La cible est absente"bksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nlgrille = Nonebksl-nlbksl-nlbksl-nldef nbpy-undlignes(grille):bksl-nl return 1000bksl-nlbksl-nlbksl-nldef nbpy-undcolonnes(grille):bksl-nl return 1000bksl-nlbksl-nlbksl-nldef donnepy-undvaleur(grille, i, j):bksl-nl global coutpy-undsecretbksl-nl coutpy-undsecret += 1bksl-nl return (1000 py-str 1000 + i py-str 1000 + j) py-str 2bksl-nlbksl-nlbksl-nlfrom random import randrangebksl-nlbksl-nlcoutpy-undsecret = 0bksl-nlresultat = recherche(randrange(1, 10py-strpy-str6), grille)bksl-nltrop = coutpy-undsecret > 2000bksl-nlassert trop == False, "Trop de tentatives"bksl-nlassert resultat is None, "La cible est absente"bksl-nlbksl-nlfor py-und in range(10):bksl-nl i0 = randrange(0, 1000)bksl-nl j0 = randrange(0, 1000)bksl-nl cible = (1000 py-str 1000 + i0 py-str 1000 + j0) py-str 2bksl-nlbksl-nl coutpy-undsecret = 0bksl-nl resultat = recherche(cible, grille)bksl-nl trop = coutpy-undsecret > 2000bksl-nl assert trop == False, "Trop de tentatives"bksl-nl assert resultat == (i0, j0), "Mauvaises coordonnées"bksl-nlbksl-nl coutpy-undsecret = 0bksl-nl resultat = recherche(cible + 1, grille)bksl-nl trop = coutpy-undsecret > 2000bksl-nl assert trop == False, "Trop de tentatives"bksl-nl assert resultat is None, "cible absente"bksl-nlbksl-nl ∞/∞

def recherche(cible, grille):bksl-nl n = nbpy-undlignes(grille)bksl-nl m = nbpy-undcolonnes(grille)bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nl# Pour ce test public grille est une liste Python,bksl-nl# mais ce ne sera pas toujours le cas !bksl-nlbksl-nlgrille = [bksl-nl [11, 33, 42, 63],bksl-nl [20, 52, 67, 80],bksl-nl [25, 61, 88, 95],bksl-nl]bksl-nlbksl-nlbksl-nldef nbpy-undlignes(grille):bksl-nl return len(grille)bksl-nlbksl-nlbksl-nldef nbpy-undcolonnes(grille):bksl-nl return len(grille[0])bksl-nlbksl-nlbksl-nldef donnepy-undvaleur(grille, i, j):bksl-nl global coutbksl-nl assert 0 <= i < 3bksl-nl assert 0 <= j < 4bksl-nl cout += 1bksl-nl return grille[i][j]bksl-nlbksl-nlbksl-nlcout = 0bksl-nlresultat = recherche(42, grille)bksl-nlassert cout <= 7, "Trop de tentatives"bksl-nlassert resultat == (0, 2), "Mauvaises coordonnées"bksl-nlbksl-nlcout = 0bksl-nlresultat = recherche(24, grille)bksl-nlassert cout <= 7, "Trop de tentatives"bksl-nlassert resultat is None, "La cible est absente"bksl-nlbksl-nldef recherche(cible, grille):bksl-nl n = nbpy-undlignes(grille)bksl-nl m = nbpy-undcolonnes(grille)bksl-nl i = 0bksl-nl j = m - 1bksl-nl while (i < n) and (j >= 0):bksl-nl x = donnepy-undvaleur(grille, i, j)bksl-nl if x > cible:bksl-nl j -= 1bksl-nl elif x < cible:bksl-nl i += 1bksl-nl else:bksl-nl return (i, j)bksl-nl return Nonebksl-nlbksl-nl

A

Pour appliquer ici une stratégie « Diviser pour régner », on identifie une case de la grille rectangulaire qui permette, soit d'avoir trouvé, soit d'éliminer une colonne, soit d'éliminer une ligne. On peut choisir ou bien la case en haut à droite, ou alors la case en bas à gauche.

Z

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.