Recherche dans une Matrice Triée

Listes de listes

Exercice Intermédiaire · Algo Express · prepa scientifique et economique (CPGE)

Enonce

Écrire une fonction qui cherche la valeur x dans une matrice M dont chaque ligne est triée. Renvoyer (i, j) si trouvé, (-1, -1) sinon.

recherche_matrice([[1, 3, 5], [7, 9, 11], [13, 15, 17]], 9) → (1, 1)
recherche_matrice([[1, 3, 5], [7, 9, 11], [13, 15, 17]], 4) → (-1, -1)

Signature attendue

def recherche_matrice(M: list, x) -> tuple:

Exemples

recherche_matrice([[1, 3, 5], [7, 9, 11], [13, 15, 17]], 9) → (1, 1)
recherche_matrice([[1, 3, 5], [7, 9, 11], [13, 15, 17]], 4) → (-1, -1)
recherche_matrice([[1, 2], [3, 4], [5, 6]], 5) → (2, 0)

Parcours en escalier

Dans une matrice où chaque ligne est triée par ordre croissant et la première valeur de chaque ligne est supérieure à la dernière de la ligne précédente, on peut chercher un élément en O(n+p) avec le parcours en escalier : on part du coin haut-droit et on descend si la valeur est trop petite, on va à gauche si elle est trop grande.

← Exercices Python pour la prépa — CPGE scientifique et ECG

Exercices du meme theme

La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.