Recherche binaire dans la matrice 2D

Question

Je me demande, peut recherche binaire être appliqué sur un tableau 2D?

• Quelles seraient les conditions sur le tableau? Trié sur 2D ??
• Quel serait le temps complexité pour cela?
• Comment l'algorithme changerait le borne de la recherche (minX, maxX, minY, maxY)?

Edit:

Recherche binaire sur 1D maintient 2 pointeurs minX et maxX .. Il sélectionne l'indice du milieu (minX+maxX)/2 et le comparer avec la valeur de recherche, si un plus grand changement alors maxX, autre changement minX .. . jusqu'à minX>=maxX

Pseudo-code binaire pour Critères de la normale:

min := 1; 
    max := N; {array size: var A : array [1..N] of integer} 
    repeat 
    mid := min + (max - min) div 2; 
    if x > A[mid] then 
     min := mid + 1 
    else 
     max := mid - 1; 
    until (A[mid] = x) or (min > max); 

Merci

Answer 1

La recherche binaire nécessite le tri de votre baie. Le tri, à son tour, nécessite une relation d'ordre totale sur les éléments du tableau. En 1-D, il est assez facile de comprendre ce que cela signifie. Je pense que vous devrez définir un index 1-D dans votre tableau à deux dimensions et vous assurer que les éléments du tableau sont triés le long de cet index.

Vous avez le choix entre plusieurs schémas d'indexation 1D, ce qui est le cas pour toute courbe de remplissage d'espace. Les plus évidents qui me viennent à l'esprit sont les suivants:

• Commencez avec le premier élément, lisez le long de chaque rangée, à la fin de chaque rangée, allez au premier élément de la rangée suivante.
• Idem, remplacez rangée par colonne.
• Une diagonalisation, dans laquelle vous lisez successivement chaque diagonale.

Comme @Bart Kiers, je ne comprends pas votre 2ème point.

Answer 2

Je pensais que ce problème de l'an dernier ... Alors, je choosed cette approche:

Tenez compte de votre 2D-tableau représente des points dans un plan. Par exemple, votre élément A [i] [j] représente un point avec x = i et y = j. Pour utiliser la recherche binaire sur le plan que je sorte tous les points à l'aide de cette condition:

point P1 < p2 si et seulement si:

• (coordonnée x de p1) < (coordonnée x de p2)
• (coordonnée x de p1) = (coordonnée x de p2) et (coordonnée y de p1) < (coordonnée y de p2)

Othwerwise p1> p2 =.Maintenant, si nous regardons notre tableau 2D, les éléments de la 2e rangée devraient être plus grands que les éléments de la 1ère rangée. Dans la même ligne, les éléments sont triés comme d'habitude (en fonction de leur numéro de colonne).

En d'autres termes:

• A [i] [j]> A [k] [j] si et seulement si (i> k). (dans différentes lignes et dans la même colonne)
• A [i] [j]> A [i] [k] si et seulement si (j> k). (dans la même ligne et dans différentes colonnes)

Considérer votre tableau a N lignes et M colonnes. Maintenant, vous devriez (temporarly) transformer votre tableau 2D à tableau 1D en utilisant cette formule (T - tableau temporaire):

for i:=0 to N-1 do 
    for j:=0 to M-1 do 
     T[i*N + j]:= A[i][j]; 

Vous avez maintenant tableau 1D. Triez-le de la manière habituelle. Et maintenant vous pouvez y chercher en utilisant un simple algorithme de recherche binaire.

Ou vous pouvez transformer votre tableau trié retour à un tableau 2D en utilisant cette formule:

for i:=0 to N*M-1 do 
    A[i div N][i - (i div N)*N]:= T[i]; 

Et utiliser deux recherches binaires:

Une recherche par coordonnées x (par lignes dans notre sens), un autre par y-coordonnée (par colonnes dans notre sens) pour les éléments dans la même rangée.

En d'autres mots, lorsque vous calculez mid = mid + (max - min) div 2, vous pouvez comparer l'élément A [mi] [0] avec votre élément clé (dans votre code, il a le nom x) et quand vous trouver la ligne avec votre élément, vous peut appeler une autre recherche binaire dans cette ligne (recherche binaire dans A [mid]).

complexité pour les deux méthodes:

• pour la recherche binaire simple dans le tableau trasformed: log (N * M)
• pour deux recherches binaires en tableau 2D: log (N) pour extérieur recherche (en lignes) + log (M) pour la recherche interne (en colonnes).

En utilisant les propriétés de la fonction logarithme nous pouvons simplifier la dernière expression: log (N) + log (M) = log (N * M). Donc, nous avons prouvé que les deux méthodes ont la même complexité et n'ont pas d'importance, celle que l'on doit utiliser.

Mais, si ce n'est pas difficile pour vous, je vous suggère de simplement transformer votre tableau en 1-D et d'utiliser une simple recherche binaire (c'est très simple et facile à déboguer et à vérifier).

Answer 3

Je l'ai résolu d'une manière simple en O(m + n) temps complexité, où m = non. de rangées et n = non des colonnes.

L'algorithme est simple: Je suis parti de coin en haut à droite (on peut aussi partir en bas à gauche) et déplacer vers la gauche si l'élément courant est supérieure à la valeur à rechercher et en bas si l'élément courant est plus petit que la valeur à rechercher.

Le code java est comme:

public static int[] linearSearch(int[][] a, int value) { 
    int i = 0, j = a[0].length - 1; // start from top right corner 

    while (i < a.length && j >= 0) { 
     if (a[i][j] == value) { 
      return new int[]{i, j}; 
     } else if (a[i][j] > value) { 
      j--; // move left 
     } else { 
      i++; // move down 
     } 
    } 
    // element not found 
    return new int[]{-1, -1}; 

} 

Gist

Vous pouvez réduire davantage la complexité de temps en utilisant une méthode appelée Improved Binary Partition.

Answer 4

Vous pouvez transformer un tableau 2D en tableau 1D et effectuer la recherche binaire ici. La complexité est O(log(m * n)) pour le tableau mxn.