Finding a value in a 2D array?

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:

1
2
3
4
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:

1
2
3
4
5
6
7
8
9
10
for(unsigned row = 0; row < Rows; ++row)
{
   for(unsigned col = 0; col < Columns; ++col)
   {
      if(SampleData[row][col] == x)
      {
         // found
      }
   }
}


Solution 2:

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


Solution 3:

1
2
3
4
5
6
7
8
int* data = &SampleData[0][0];
for(unsigned i = 0; i < Rows * Columns; ++i)
{
   if(*data++ == x)
   {
      // found
   }
}
Last edited on
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.

Registered users can post here. Sign in or register to post.