Quickest way to determine if a 2D array contains an element?

Question

Let's assume that I've got 2d array like :

int[,] my_array = new int[100, 100];

The array is filled with ints. What would be the quickest way to check if a target-value element is contained within the array ?

(* this is not homework, I'm trying to come up with most efficient solution for this case)

Answer 1

If the array isn't sorted in some fashion, I don't see how anything would be faster than checking every single value using two for statements. If it is sorted you can use a binary search.

Edit: If you need to do this repeatedly, your approach would depend on the data. If the integers within this array range only up to 256, you can have a boolean array of that length, and go through the values in your data flipping the bits inside the boolean array. If the integers can range higher you can use a HashSet. The first call to your contains function would be a little slow because it would have to index the data. But subsequent calls would be O(1).

Edit1:

This will index the data on the first run, benchmarking found that the Contains takes 0 milliseconds to run after the first run, 13 to index. If I had more time I might multithread it and have it return the result, while asynchronously continuing indexing on the first call. Also since arrays are reference types, changing the value of data passed before or after it has been indexed will provide strange functionality, so this is just a sample and should be refactored prior to use.

private class DataContainer
{
    private readonly int[,] _data;
    private HashSet<int> _index;

    public DataContainer(int[,] data)
    {
        _data = data;
    }

    public bool Contains(int value)
    {

        if (_index == null)
        {
            _index = new HashSet<int>();
            for (int i = 0; i < _data.GetLength(0); i++)
            {
                for (int j = 0; j < _data.GetLength(1); j++)
                {
                    _index.Add(_data[i, j]);
                }
            }
        }
        return _index.Contains(value);
    }
}

Answer 2

create a hash out of the 2d array, where

1 --> 1st row 2 --> 2nd row ... n --> nth row

O(n) to check the presence of a given element, assuming each hash check gives O(1).

This data structure gives you an opportunity to preserve your 2d array.

upd: ignore the above, it does not give any value. See comments

Answer 3

Assumptions:

• There is no kind of ordering in the arrays we can take advantage of
• You are going to check for existence in the array several times

I think some kind of index might work nicely. If you want a yes/no answer if a given number is in the array. A hash table could be used for this, giving you a constant O(k) for lookups.

Also don't forget that realistically, for small MxN array sizes, it might actually be faster just to do a linear O(n) lookup.

Answer 4

You could encapsulate the data itself, and keep a Dictionary along with it that gets modified as the data gets modified.

The key of the Dictionary would be the target element value, and the value would be the number of entries of the element. To test if an element exists, simply check the dictionary for a count > 0, which is somewhere between O(1) and O(n). You could also get other statistics on the data much quicker with this construct, particularly if the data is sparse.

The biggest drawback to this solution is that data modifications have more operations involved (still should be O(1), though), so if you're mostly doing data manipulation, then this might not be suitable.