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)

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

Solution 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

Solution 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.