Поиск в многомерном массиве в C #

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

Учитывая, что массив отсортирован в лексическом порядке, у вас есть две опции:

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

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

Если массив отсортирован, вы можете использовать бинарный поиск.

Встроенный метод Array.BinarySearch обрабатывает только одномерные массивы, поэтому вы должны реализовать его самостоятельно.