搜索

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