Finding a value in a 2D array?

[DreamCore]

Hi!

I want to search a 2D array to see if it contains a certain value x. I can come up with three different ways to do this. Provided I have:

const int Rows = 40;
const int Columns = 30;

int SampleData[Rows][Columns] = { ... }

Is there any real difference (in terms of performance etc.) between these, or are there an even better solution?

Solution 1:

for(unsigned row = 0; row < Rows; ++row)
{
   for(unsigned col = 0; col < Columns; ++col)
   {
      if(SampleData[row][col] == x)
      {
         // found
      }
   }
}

Solution 2:

int* data = &SampleData[0][0];
if(find(data, data + Rows * Columns, x) != data + Rows * Columns)
{
   // found
}

Solution 3:

int* data = &SampleData[0][0];
for(unsigned i = 0; i < Rows * Columns; ++i)
{
   if(*data++ == x)
   {
      // found
   }
}

[TwilightSpectre]

They would all be fairly similar in terms of performance. Solution 1 and 3 should be about the same in terms of performance, Solution 3 may be very slightly better (not enough to matter) (assuming no optimizations). On some implementations, Solution 2 could be the fastest, due to the implementation of std::find containing some sort of loop unrolling. Of course, this is implementation dependent, but it should always be at least as fast as Solution 1 and 3.

I can't think of a better way of doing this off the top of my head. However, if you were going to be searching to see if the array contained a whole bunch of values, as in searching a number of times, you would be best off to sort the sequence (out-of-place and 1 dimensional, if you want to keep the original) and then use something like std::binary_search as a quick way of finding the value. Of course, due to the cost of sorting, you'll need to do some tests to see if its worth it or not.