Search a 2D Matrix
Vous disposez d’une grille d’entiers matrix comportant m lignes et n colonnes, ainsi que d’un entier target. Chaque ligne est triée par ordre croissant, et la première valeur de chaque ligne est supérieure à la dernière valeur de la ligne au-dessus. Renvoyez true si target apparaît dans la grille et false sinon, en temps O(log(m × n)).
Fonction
- matrixinteger-2d-array
- la grille, donnée sous forme de liste de lignes, triées ligne par ligne
- targetinteger
- la valeur à rechercher
- Renvoieboolean
- vrai si la cible se trouve dans la grille, faux sinon
Contraintes
1 ≤ m, n ≤ 100, oùm = matrix.lengthetn = matrix[i].length- Chaque ligne a la même longueur
n. -104 ≤ matrix[i][j], target ≤ 104- Chaque ligne est triée par ordre strictement croissant, et la première valeur de chaque ligne est supérieure à la dernière valeur de la ligne précédente.
Exemples
- Entrée
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 26
- Sortie
- true
- Explication
- Lus ligne par ligne, les 12 valeurs forment une seule liste triée. Une recherche binaire sur les positions de 0 à 11 vérifie 21 à la position 5 (trop petit), 33 à la position 8 (trop grand), puis trouve 26 à la position 6.
- Entrée
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 16
- Sortie
- false
- Explication
- 16 viendrait après 14, la dernière valeur de la ligne 0, et avant 17, la première valeur de la ligne 1. Rien ne se trouve entre les deux, donc 16 ne figure pas dans la grille.
Pour aller plus loin
Supposons que les lignes puissent avoir des longueurs différentes, tout en étant triées bout à bout. Comment convertiriez-vous une position en ligne et en colonne, et quel serait le coût de la recherche ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Lisez la matrice ligne par ligne, de gauche à droite, comme s’il s’agissait d’une longue liste. Que remarquez-vous à propos de l’ordre des valeurs dans cette liste ?
Ensemble, ces deux règles signifient que la matrice entière, lue ligne par ligne, forme une liste triée de
m × nvaleurs. Tu peux y effectuer une recherche binaire sans jamais la construire.Effectuez une recherche binaire sur les positions
0àm × n - 1. La positionpse trouve à la lignep / net à la colonnep % n(division entière) ; chaque étape lit une cellule et élimine la moitié des positions restantes.
Solution
Les deux règles d’ordre réunies font de la grille, lue ligne par ligne, une liste triée de m × n valeurs. Effectuez une recherche binaire dans cette liste par position, puis convertissez chaque position en une ligne et une colonne à l’aide d’une division. Une grille de 100 par 100 ne nécessite alors que 14 comparaisons au maximum, au lieu de 10000.
Vérifie chaque cellule
Intuition
Comparez chaque cellule à target et renvoyez true en cas de correspondance, false après la dernière cellule. Cette méthode lit chaque cellule, elle est donc correcte pour n’importe quelle grille, triée ou non. Elle n’utilise jamais l’ordre, donc une grille de 100 sur 100 nécessite jusqu’à 10000 comparaisons.
Algorithme
- Pour chaque ligne de
matrix, examine chaque valeur dans l’ordre. - Si la valeur est égale à
target, retournetrue. - Après les boucles, retourne
false.
def searchMatrix(matrix, target):
for row in matrix:
for value in row:
if value == target:
return True
return FalseMarchez depuis le coin supérieur droit
Intuition
À partir de la cellule en haut à droite, chaque valeur située à gauche est plus petite et chaque valeur située en dessous est plus grande. Si la cellule est plus grande que target, la colonne en dessous l’est aussi : avancez vers la gauche et éliminez cette colonne. Si elle est plus petite, la ligne à sa gauche l’est aussi : descendez et éliminez cette ligne.
Dans le premier exemple, 14 est plus petit que 26, alors descendez jusqu’à 30. 30 est plus grand, alors avancez vers la gauche jusqu’à 26, qui correspond à la cible. Chaque étape élimine une ligne ou une colonne, donc vous faites au plus m + n étapes : 200 pour une grille de 100 sur 100. Cette recherche nécessite seulement que les lignes et les colonnes soient triées, donc elle ne tire pas parti de la moitié des propriétés de cette grille.
Algorithme
- Commence à la ligne
0et à la dernière colonne. - Tant que la ligne et la colonne restent dans la grille, lis la cellule.
- Si elle est égale à
target, renvoietrue. - Si elle est plus grande, déplace-toi d’une colonne vers la gauche ; si elle est plus petite, déplace-toi d’une ligne vers le bas.
- Lorsque tu sors de la grille, renvoie
false.
def searchMatrix(matrix, target):
# Start at the top-right corner: left is smaller, down is larger.
r, c = 0, len(matrix[0]) - 1
while r < len(matrix) and c >= 0:
value = matrix[r][c]
if value == target:
return True
if value > target:
c -= 1 # every value below in this column is larger still
else:
r += 1 # every value to the left in this row is smaller still
return FalseRecherche binaire sur la grille aplatie
Intuition
Numérotez les cellules ligne par ligne : la ligne 0 contient les positions de 0 à n - 1, la ligne 1 contient les positions de n à 2n - 1, et ainsi de suite. Chaque ligne est triée et commence après la fin de la ligne précédente, les valeurs ne font donc qu’augmenter avec la position. Il s’agit d’une liste triée, et la recherche binaire s’applique.
Vous ne construisez jamais la liste. La position p se trouve à la ligne p / n et à la colonne p % n, avec une division entière. Dans le premier exemple, n = 4, donc la position 6 correspond à la ligne 1, colonne 2, qui contient 26. Chaque comparaison divise par deux le nombre de positions susceptibles de contenir target : au plus 14 pour 10000 cellules, avec deux index de mémoire supplémentaire.
Algorithme
- Soient
metnle nombre de lignes et de colonnes, et définissezlo = 0,hi = m × n - 1. - Tant que
lo ≤ hi, prenezmidà mi-chemin entre les deux. - Lisez
value = matrix[mid / n][mid % n]. - Si
valueest égal àtarget, renvoyeztrue. S'il est plus petit, définissezlo = mid + 1; sinon, définissezhi = mid - 1. - Lorsque la boucle se termine, renvoyez
false.
def searchMatrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
# Read row by row, the cells form one sorted list of rows * cols values.
# Position p of that list is matrix[p // cols][p % cols].
lo, hi = 0, rows * cols - 1
while lo <= hi:
mid = (lo + hi) // 2
value = matrix[mid // cols][mid % cols]
if value == target:
return True
if value < target:
lo = mid + 1
else:
hi = mid - 1
return False
Pièges et cas limites
- Diviser par le nombre de lignes au lieu du nombre de colonnes. La position
pse trouve sur la lignep / n; en mettantmà sa place, le code fonctionne sur les grilles carrées et échoue sur une grille de 3 lignes et 4 colonnes. - Dans la version avec deux recherches, ne pas gérer le cas où
targetest inférieur àmatrix[0][0]. Aucune ligne ne commence à cette valeur ou en dessous, et un indice de ligne égal à-1est transmis à la deuxième recherche. - Utiliser une boucle avec
lo < hiet unhiinclusif. Une grille de 1 sur 1 contenanttargetrenvoiefalse, car la boucle ne s'exécute jamais. - En Lua et en R, oublier le décalage nécessaire pour les index commençant à 1 : la position
pse trouve sur la lignep / n + 1, colonnep % n + 1.
Questions fréquentes3
Quelle est la complexité temporelle de la recherche dans une matrice 2D ?
La recherche binaire dans la grille aplatie s’exécute en O(log(m × n)) et utilise un espace O(1) : au plus 14 comparaisons pour 10000 cellules. Comme log(m × n) = log m + log n, cela équivaut à rechercher la ligne, puis à effectuer la recherche à l’intérieur de celle-ci.
Faut-il utiliser la marche depuis le coin supérieur droit ou la recherche binaire ?
Le parcours par les coins prend O(m + n) étapes et nécessite seulement que les lignes et les colonnes soient triées ; il résout donc aussi la variante où une ligne peut commencer sous la fin de la ligne précédente. Lorsque chaque ligne commence au-dessus de l’endroit où se termine la précédente, comme ici, la recherche binaire est plus rapide.
Est-ce que deux recherches binaires, l’une pour la ligne et l’autre à l’intérieur de celle-ci, sont également correctes ?
Oui. Effectuez une recherche binaire dans la première colonne pour trouver la dernière ligne dont la première valeur est inférieure ou égale à target, puis effectuez une recherche binaire dans cette ligne. La complexité est de O(log m + log n), soit la même borne. La recherche unique effectue le même travail avec une seule boucle et moins de cas particuliers.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def searchMatrix(matrix, target):
# Écrivez le code iciTest #1
Test #2
Arguments
matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]] target = 26
Résultat attendu
true