L'algorithme de recherche de matrice en Python

Défi :Comment trouver un élément dans une matrice triée où les valeurs des lignes et des colonnes augmentent de façon monotone ?

Qu'est-ce qu'une matrice ? Une matrice est un tableau de valeurs composé de lignes et de colonnes. Ici, nous représentons la matrice comme une liste de listes d'entiers. Par conséquent, nous pouvons accéder aux valeurs de la matrice avec la notation d'indexation et de découpage.

Comment trouver un élément dans une matrice en Python ?

L'algorithme naïf pour trouver un élément dans une matrice Python consiste à parcourir toutes les lignes et valeurs de ces lignes et à comparer ces éléments à la valeur recherchée :

def matrix_find(matrix, value):
    for row in matrix:
        for element in row:
            if element == value:
                return True
    return False
            

matrix = [[3, 4, 4, 6],
          [6, 8, 11, 12],
          [6, 8, 11, 15],
          [9, 11, 12, 17]]

print(matrix_find(matrix, 7))
# False

print(matrix_find(matrix, 17))
# True

Si la matrice a n rangées et m colonnes, la complexité d'exécution de l'algorithme est O(n*m) parce que vous devez effectuer n*m comparaisons. Ce n'est pas optimal pour un trié matrice (voir plus loin) !

Comment trouver un élément dans une matrice triée en Python ?

Qu'est-ce qu'un trié matrice ? La matrice est triée car les nombres entiers dans les lignes et les colonnes augmentent de manière monotone avec le numéro de ligne et de colonne.

L'algorithme de recherche de matrice est une belle façon de rechercher une valeur dans une matrice triée sans visiter toutes les valeurs de la matrice triée.

Voici l'algorithme :

def matrix_find(matrix, value):
    if not matrix or not matrix[0]:
        return False

    j = len(matrix) - 1
    for row in matrix:
        while row[j] > value:
            j = j - 1
            if j == -1:
                return False
        if row[j] == value:
            return True
    return False

matrix = [[3, 4, 4, 6],
          [6, 8, 11, 12],
          [6, 8, 11, 15],
          [9, 11, 12, 17]]
print(matrix_find(matrix=matrix, value=7))

La fonction matrixFind prend une matrice entière triée et une valeur entière. Il renvoie True si la matrice contient la valeur entière.

Explication

Dans les premières lignes, l'algorithme vérifie si la matrice est vide et renvoie False si tel est le cas.

Ensuite, la boucle while itère sur les lignes i et la colonne j de la matrice commençant par la première ligne i=0 et la dernière colonne j=n-1 .

Mais au lieu de chercher dans toute la matrice, l'algorithme utilise une stratégie plus intelligente. Il ignore des lignes et des colonnes entières à la fois avec la méthode suivante.

Vérifiez la dernière valeur de la première ligne (valeur de matrice en haut à droite). Nous désignons cette valeur par matrix[i][j] . Il y a trois cas.

1. La valeur de matrice en haut à droite matrix[i][j] est égal à la valeur recherchée. Dans ce cas, l'algorithme renvoie True .
2. La valeur de matrice en haut à droite matrix[i][j] est inférieur à la valeur recherchée. Étant donné que la matrice est triée, la valeur de la matrice en haut à droite est le plus grand élément de la ligne i. Ainsi, nous pouvons ignorer complètement la ligne i en passant à la ligne suivante i = i+1 . Ensuite, nous répétons cette procédure avec une matrice plus petite qui a une ligne de moins (c'est-à-dire la ligne i).
3. La valeur de matrice en haut à droite matrix[i][j] est supérieur à la valeur recherchée. Cela signifie que toute la colonne j ne contient que des éléments supérieurs à la valeur recherchée. Ainsi, nous sommes sûrs que notre valeur recherchée n'est pas dans la colonne j et nous pouvons ignorer complètement cette colonne en diminuant j = j-1 . Ensuite, nous répétons cette procédure avec une matrice plus petite qui a une colonne de moins (c'est-à-dire la ligne j).

Matrice de complexité d'exécution – Recherche

En résumé, l'idée de ce grand algorithme de Keith Schwartz réduit une ligne ou une colonne à chaque itération. Le temps d'exécution est seulement O(2n) au lieu de O(n^2) pour une matrice carrée à n lignes et colonnes.

Puzzle Matrix-Trouver

Testez votre compréhension en résolvant le casse-tête Python suivant sur notre application Finxter :

Êtes-vous un codeur maître?
Testez vos compétences maintenant !

Vidéo associée

Humour de programmeur

Il n'y a que 10 types de personnes dans ce monde :ceux qui connaissent le binaire et ceux qui ne le connaissent pas.
👩🧔‍♂️
~~~

Il existe 10 types de personnes dans le monde. Ceux qui comprennent le trinaire, ceux qui ne le comprennent pas et ceux qui le confondent avec le binaire.
👩🧔‍♂️👱‍♀️