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 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