Recherche binaire dans le Tableau 2D
Je me demande, peut binaire de recherche être appliqué sur un tableau 2D?
- Que serait le conditions sur le tableau? Triés sur de la 2D??
- Ce serait le moment complexité?
- Comment la modification de l'algorithme de la limites de la recherche (minX,maxX,minY,maxY) ??
Edit:
Binaire de Recherche sur les 1D maintient 2 pointeurs minX
et maxX
..
Il sélectionne le moyen de l'indice de (minX+maxX)/2
et de la comparer avec la valeur de recherche, si elle est supérieure, puis changer maxX
, d'autre changement minX
... jusqu'à ce que minX>=maxX
Pseudo-code binaire normal seacrh:
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);
Grâce
Est-il quelque chose en particulier que vous voulez réaliser?
Ma première recommandation serait d'obtenir votre 1D algorithme travaillé. Il peut y avoir quelques problèmes de limites. Considérons un tableau de taille 1. Ici
C'est juste le code dans Wikipedia... Il n'a pas d'importance c'est juste pour la démonstration..
A juste pris un second regard... Mon erreur:
Dans mon cas, j'ai une liste de points 2D où X=la pression et Y=la température. Compte tenu de l'entrée targetKey (X,Y) j'ai besoin de trouver le plus proche de la targetKey dans l'ensemble de données. Au début, je pensais que je pouvais utiliser un BinarySearch, mise en œuvre d'une coutume de comparer le type, qui compare la distance entre deux points. Cependant cela ne fonctionne pas, car il fallait attendre la liste à être re-triés dans l'ordre de la distance de la targetKey avant l'exécution de chaque Binaire de Recherche. Une meilleure solution est d'utiliser un quadtree. Pour info, C# de la mise en œuvre est ici: lien
Ma première recommandation serait d'obtenir votre 1D algorithme travaillé. Il peut y avoir quelques problèmes de limites. Considérons un tableau de taille 1. Ici
min = 1
et max = 1
. Puis mid := min + (max - min) div 2
résultats dans mid = 0
(en supposant que l'arithmétique des nombres entiers). Alors qui sait ce que A[mid]
équivaut à (donnée A
est indexé comme: 1..N).C'est juste le code dans Wikipedia... Il n'a pas d'importance c'est juste pour la démonstration..
A juste pris un second regard... Mon erreur:
mid := min + (max - min) DIV 2
résultats dans 1, ce qui est tout simplement parfait.Dans mon cas, j'ai une liste de points 2D où X=la pression et Y=la température. Compte tenu de l'entrée targetKey (X,Y) j'ai besoin de trouver le plus proche de la targetKey dans l'ensemble de données. Au début, je pensais que je pouvais utiliser un BinarySearch, mise en œuvre d'une coutume de comparer le type, qui compare la distance entre deux points. Cependant cela ne fonctionne pas, car il fallait attendre la liste à être re-triés dans l'ordre de la distance de la targetKey avant l'exécution de chaque Binaire de Recherche. Une meilleure solution est d'utiliser un quadtree. Pour info, C# de la mise en œuvre est ici: lien
OriginalL'auteur Betamoo | 2010-12-12
Vous devez vous connecter pour publier un commentaire.
Je l'ai résolu de manière simple
O(m + n)
temps de la complexité, où m = n. de lignes et n = non. des colonnes.Le code java est comme:
Résumé
Vous pouvez réduire la complexité du temps en utilisant une méthode appelée Amélioration de la Partition Binaire.
OriginalL'auteur Ram Patra
J'ai pensé à ce problème l'année dernière... Donc, j'avais choisi cette approche:
Tenir 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. D'utiliser les binaires de recherche sur le plan que je sorte tous les points à l'aide de cette condition:
point p1 < p2 si et seulement si:
Othwerwise p1 >= p2.
Maintenant, si nous regardons notre 2D-tableau, les éléments dans la 2e rangée devrait être plus grand que les éléments en 1ère ligne. Dans la même ligne d'éléments triés comme d'habitude (en fonction de leur numéro de colonne).
En d'autres termes:
Tenir compte de votre matrice de N lignes et M colonnes. Maintenant, vous devriez (temporairement) de transformer votre tableau 2D à 1D tableau à l'aide de cette formule (T - tableau temporaire):
Maintenant, vous avez 1D tableau. Le tri dans la manière habituelle. Et maintenant, vous pouvez effectuer une recherche à l'aide de simples binaire de l'algorithme de recherche.
Ou vous pouvez transformer votre tableau trié de retour à la 2D tableau à l'aide de cette formule:
Et l'utilisation de deux binaires de recherche:
Une recherche par x-coordonnée (par lignes dans notre sens), un autre en abscisse (en colonnes dans notre sens) pour les éléments d'une même ligne.
En d'autres termes, 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 x nom) et quand vous trouver la ligne avec votre élément, vous pouvez appeler une autre recherche binaire dans cette ligne (recherche binaire dans Un[mi]).Complexité pour les deux méthodes:
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 l'avons prouvé, que les deux méthodes ont la même complexité et n'a pas d'importance, celle à utiliser.
Mais, si il n'est pas difficile pour vous, je vous suggère tout simplement de transformer votre tableau 1-D et à l'utilisation simple recherche binaire (c'est très simple et facile à déboguer et à vérifier).
OriginalL'auteur Ilnur
Binaire des travaux de Recherche dans les diviser et conquérir façon,
Nous allons garder une itération de la boucle while, à chaque fois que nous la mise à jour de début et de fin de l'index selon les exigences..
while(start <= fin){
Si la valeur actuelle est égale à la recherche de l'élément de ensuite, nous avons juste à imprimer et à retourner.
Si la valeur actuelle est inférieure à la recherche de l'élément de ensuite, nous avons juste à mettre à jour la valeur moyenne par mi = mi + 1
Si la valeur actuelle est supérieur à la recherche de l'élément de ensuite, nous avons juste à mettre à jour la valeur moyenne par mi = mi - 1
OriginalL'auteur Maulik Sakhida
Binaire de recherche nécessite que votre tableau soit trié. Le tri, à son tour, exige une relation de tri 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 1-D index dans votre tableau 2d et de s'assurer que les éléments du tableau sont triées au long de l'indice.
Vous avez une variété d'1-D de l'indexation des régimes de choisir à partir, essentiellement, toute courbe de remplissage d'espace ne pourra le faire. Le évidentes qui viennent à l'esprit sont:
Comme @Bart Kiers, je ne comprends pas votre 2ème point.
J'ai regardé la question modifiée. Maintenant, le point que je ne comprends pas, c'est le 3ème pas 2ème.
OriginalL'auteur High Performance Mark
Vous pouvez le transformer en tableau 2D en 1D tableau et de faire de la recherche binaire ici. La complexité est
O(log(m * n))
pourmxn
tableau.OriginalL'auteur Thanh Nguyen Dai