搜索

Question

我有

int[,] PDATVL = new int[100,2]; 

多维数组让虚拟数据是：

249 398 
249 423 
249 448 
249 473 
249 498 
251 17 
251 42 
251 325 
252 142 
252 418 
253 194 
254 7 
254 319 
255 81 
255 378 

现在我想在数组中搜索251，142对。 除线性搜索外，最佳方法是什么？

Answer 1

如果对数组进行排序，则可以使用二分搜索。

内置的方法Array.BinarySearch只能处理一维数组，所以你必须自己实现它。

Answer 2

如果您正在使用对工作，如果不是，为什么不使用结构

HashSet<KeyValuePair<int, int>> 

或

List<KeyValuePair<int, int>> 

在.NET 4

然后你就可以搜索一对这样的：

pairs.Where(p=> p.Key == 251 && p.Value == 142); 

Answer 3

如果每个所述对中的值中的最大值，则可以将它们组合成一个单一的值，像这样：

long pair = value1 * 10000000 + value2; // assuming value2 < 1000000 

，然后将它们存储在词典（或HashSet的在.NET 4） ，使搜索O（1）：

var d = new Dictionary<long, object>; 
long pair1 = 251 * 1000000 + 142; 
d.Add(pair1, null); 
long pair 2 = .... 
// ... 

var exists = d.ContainsKey(pair1); 

Answer 4

鉴于阵列词汇顺序排序，你有两个选择：

1. 编写了两工作的自定义的二进制搜索方法二维数组。
2. 写存储一对整数并实现IComparable<T>和IEquatable<T>

我会去选择两个结构。这种结构的基本实现是：

public struct Pair : IComparable<Pair>, IEquatable<Pair> 
{ 
    private readonly int x; 
    private readonly int y; 

    public Pair(int x, int y) 
    { 
     this.x = x; 
     this.y = y; 
    } 

    public int X { get { return x; } } 
    public int Y { get { return y; } } 

    public int CompareTo(Pair other) 
    { 
     return (x == other.x) ? y.CompareTo(other.y) : x.CompareTo(other.x); 
    } 

    public bool Equals(Pair other) 
    { 
     return x == other.x && y == other.y; 
    } 
} 

现在你可以使用Array.BinarySearch方法：

var pairs = new[] {new Pair(1, 1), new Pair(1,2), new Pair(1, 3), new Pair(2, 3), new Pair(2, 4)}; 

// Returns 2 
int index1 = Array.BinarySearch(pairs, new Pair(1,3)); 

// No match. Returns a negative number. 
int index2 = Array.BinarySearch(pairs, new Pair(1, 4));