élément de recherche dans un tableau 2d

Question

J'ai récemment assis dans une interview et je pose cette question:

Étant donné un tableau 2D d'entiers, où:

• Chaque ligne est triée de gauche à droite.

• Chaque colonne est triée de haut en bas.

Quel est le meilleur algorithme pour trouver la position d'un élément x?

j'étais heureux, comme je l'avais fait auparavant, et ce fut ma réponse:

Démarrer à la position en haut à droite.

Si e à cette position est supérieur à x, alors définitivement, tous les éléments de cette colonne sont supérieurs à x et on recule d'une colonne.

Si e à cette position est inférieure à x, puis définitivement tous les éléments derrière e sont inférieurs à x et tous les éléments après e sont supérieurs à x et donc nous déplacer d'une ligne vers le bas,

Si e == x, nous nous arrêtons ou nous continuons jusqu'à ce que nous atteignions la limite gauche ou la limite inférieure et si nous frappons une limite avant que nous trouvions e == x, alors le tableau 2d ne contient pas cet élément.

De toute évidence, la complexité temporelle de cette méthode est O (n) pour la matrice nXn, mais l'intervieweur a insisté sur une approche logrithmic, et je ne pouvais pas atteindre ne importe où près O (log n).

Ma question est, peut-elle être faite en O (log n)?

Answer 1

Oui, cela peut être fait, il suffit de faire une recherche binaire.

public int searchMatrix(ArrayList<ArrayList<Integer>> A, int B) { 
    int row, col; 
    int m, n; 
    if (A == null) 
     return 0; 
    m = A.size(); 
    if (m == 0) 
     return 0; 
    n = A.get(0).size(); 
    row = 0; 
    col = n - 1; 
    while (checkBound(row, col, m, n)) { 
     if (B == A.get(row).get(col)) 
      return 1; 
     int num = A.get(row).get(col); 

     if (B < num) 
      col--; 
     else if (B > num) 
      row++; 
    } 
    return 0; 
} 

public boolean checkBound(int row, int col, int m, int n) { 
    return (row >= 0 && row < m && col >= 0 && col < n); 

}