CODEWITHSUNDEEP
c#.netlinqsearchmultidimensional-array
user696775
user696775

Reputation: 31

Search in multidimensional array in C#

I has multidimensional array of 

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

Let dummy data be:

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

Now I want to search for 251, 142 pair in the array. What will be the best approach for this except linear search.

Upvotes: 2

Views: 5392

Answers (4)

James Kyburz
James Kyburz

Reputation: 14453

If you are working with pairs why not use the structure

HashSet<KeyValuePair<int, int>>

or 

List<KeyValuePair<int, int>>

if not in .NET 4.

Then you can search a pair like this:

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

Upvotes: 2

Elian Ebbing
Elian Ebbing

Reputation: 19027

Given that the array is sorted in lexical order, you have two options:

  1. Write a custom binary search method that works with a two-dimensional array.
  2. Write a struct that stores a pair of integers and implements IComparable<T> and IEquatable<T>

I would go for option two. A basic implementation for such a struct would be:

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

Now you can use the Array.BinarySearch method:

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

Upvotes: 2

abieganski
abieganski

Reputation: 560

If there is a maximum value of each of the values in the pair, then you could combine them into a single value, like so:

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

and then store them in a Dictionary (or HashSet in .NET 4), so that searching is 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);

Upvotes: 1

Guffa
Guffa

Reputation: 700322

If the array is sorted, then you can use binary search.

The built in method Array.BinarySearch only handles one-dimensional arrays, so you have to implement it yourself though.

Upvotes: 1

Related Questions