Convert 1D Array search to 2D Array Search

[gamerchick]

Does Anyone know how i can convert this 1D array (findArray) that checks for an element Into a function called 2Dfind that searches a 2D and pass each array to arrayfind(), to do the searching

int findArray(int A[], int n, int x)
{
   for(int i = 0; i < n; i++)
     if(A[i] == x)
       return i;
     else
       return -1;
}

ive been told i dont need to use another for loop but im still unsure how to make this new 2Dfind Function

i tried this but i was told its wrong

int 2Dfind(int A[][], int &n, int &x)
{
	for(int i = 0; i < n; i++)
	{
 		for(int j=0; j < n[i]; j++)
  		{
			if(A[i][j] == x)
				return i,j;
					else
					    return -1;
		}
	}
}

[hag++]

You do need a second for loop (one for the rows, one for the columns, in the array) It may be easier to use pointers:

int* return_ptr(int str[][20], int x, int max_rows, int max_col) {
	int* a_ptr = new int;

	for (int i = 0; i < max_rows; i++)
	{
		for (int j = 0; j < max_col; j++)
		{
			if (str[i][j] == x)		
			         return a_ptr = &str[i][j];
		}
	}
                return NULL;
}

[abdelhakeem]

int 2Dfind(int A[][], int &n, int &x)

First:
Your variable can't start with a digit like you've started it with '2'.
A better would be FindIn2D or else ,but not starting with a digit.

Second:
Use templates better to be applied on all kinds of 2D-Arrays and specialize it for char arrays because thier comparison algorithm differs.

Try it again but take care of these mistakes ,And if you're stucked in something we will be glad to help you.

,,,
Kimo

[gamerchick]

yes but the question says i have to call findArray within the new function find2D

ex: pseudocode

function find2D, finds an element x in an n × n array A. The
function find2D iterates over the rows of A, and it calls the function
findArray shown above, on each one, until x is found or it has searched all rows of A

[gamerchick]

yes but the question says i have to call findArray within the new function 2Dfind

ex: pseudocode

function 2Dfind, finds an element x in an n × n array A. The
function 2Dfind iterates over the rows of A, and it calls the function
findArray shown above, on each one, until x is found or it has searched all rows of A

[hag++]

Does Anyone know how i can convert this 1D array (findArray) that checks for an element Into a function called 2Dfind that searches a 2D and pass each array to arrayfind(), to do the searching

int findArray(int A[], int n, int x)
{
   for(int i = 0; i < n; i++)
     if(A[i] == x)
       return i;
     else
       return -1;
}

ive been told i dont need to use another for loop but im still unsure how to make this new 2Dfind Function

i tried this but i was told its wrong

int 2Dfind(int A[][], int &n, int &x)
{
	for(int i = 0; i < n; i++)
	{
 		for(int j=0; j < n[i]; j++)
  		{
			if(A[i][j] == x)
				return i,j;
					else
					    return -1;
		}
	}
}

It is wrong. The reason being is return i,j; You cannot return 2 values this way. In order to return 2 values you need to "package" them in a way that you are returning multiple peices of info in only one value, which is why it would be easier using pointers. You could also use structures or reference variables

[hag++]

yes but the question says i have to call findArray within the new function find2D

ex: pseudocode

function find2D, finds an element x in an n × n array A. The
function find2D iterates over the rows of A, and it calls the function
findArray shown above, on each one, until x is found or it has searched all rows of A

Ok so you need two functions that both accept the 2 dimensional array. One function will update the "row" count and call the second function, which searches ONLY the specified row, but ALL columns in that row. The second function either returns the desired value or returns some kind of value indicating "value not found"

[gamerchick]

It is wrong. The reason being is return i,j; You cannot return 2 values this way. In order to return 2 values you need to "package" them in a way that you are returning multiple peices of info in only one value, which is why it would be easier using pointers. You could also use structures.

he told me it was wrong because the second for loop being n is searching a object that has no elements inside, the returning parts not rly my issue all i need to understand is how to pass each array from find2D function to arrayFind() to do the searching

[hag++]

he told me it was wrong because the second for loop being n is searching a object that has no elements inside, the returning parts not rly my issue all i need to understand is how to pass each array from find2D function to arrayFind() to do the searching

See my post right above yours :) and two, it depends on what your instructor wants. You either use two for loops in the same function to search the array ( I put an example on the top of the forum, the one using the pointers) OR follow the pseudocode on my last post before this

[mrnutty]

You do need a second for loop (one for the rows, one for the columns, in the array) It may be easier to use pointers:

int* return_ptr(int str[][20], int x, int max_rows, int max_col) {
	int* a_ptr = new int;

	for (int i = 0; i < max_rows; i++)
	{
		for (int j = 0; j < max_col; j++)
		{
			if (str[i][j] == x)		
			         return a_ptr = &str[i][j];
		}
	}
}

Not a good idea. It could potentially cause a memory leak.

Do something like this :

const int Row = 5;
 const int Col = 5;

struct SearchInfo{
 static const  int INVALID = -1;
 size_t row_;
 size_t col_;
 SearchInfo() { row_ = col_ = INVALID; }
}

SearchInfo find(int *Array[Col], const int Key, const int MR, const int MC){
  SearchInfo ret;
 for(int i = 0; i != MR; ++i )
      for(int j = 0; j != MC; ++j){ 
        if(Array[i][j] == key){
                ret.row_ = i; 
                ret.col_ = j; 
             break;
     }
     return ret;
}
int main()
{
  int Array2D[Row][Col] = { {0} };
  SearchInfo info = find(Array2D, 0, Row, Col );
  return 0;
}

Or if you want to represent 2d array as 1d then you can do this :

const int Row = 4;
const int Col = 4;
int find(int * Array,const int key,const int row,const int col){
  int ret = -1;
 for(int i = 0; i < row * col ; ++i){
         if(Array[i] == key) {
              ret = i;
              break;
        }
  }
 return ret;
}
int main()
{
  int Array[Row * Col] = {0};
  int indx = find(Array,0,Row,Col);
  return 0;
}

All the above code was not compiled so you probably will find a mistake.

[nezachem]

Ok so you need two functions that both accept the 2 dimensional array.

Why?

One function will update the "row" count and call the second function, which searches ONLY the specified row, but ALL columns in that row. The second function either returns the desired value or returns some kind of value indicating "value not found"

find2d does need to accept a 2d array. Then it passes one row at a time down to find1d. Am I missing something?

[abdelhakeem]

I hope this one will help you, I'm using templates with in it, so if you want to search for (char *)'s you need to specialize it for (char *)'s.

Here's the code:

template<class T>
pair<int, int> FindIn2D(const T *TwoDArray, int rows, int cols, const T ToSearch)
{
    for (int r=0 ; r<rows ; ++r)
    for (int c=0 ; c<cols ; ++c)
    {
        if(TwoDArray[r*cols+c] == ToSearch) return make_pair(r, c);
    }

    return make_pair(-1, -1);
}

When you use it to search in a 2D-Array you have to pass the address of the first element in the first row, or the first row e.g:

FindIn2D(&arr[0][0], 3, 5, 'B')

or:

FindIn2D(arr[0], 3, 5, 'B')

And to deal with the return values use this for row number:

cout << FindIn2D(arr[0], 3, 5, 'B').first;

And this for column number:

cout << FindIn2D(arr[0], 3, 5, 'B').second;

Hope this helped :)
,,,
Kimo

[gamerchick]

Why?

find2d does need to accept a 2d array. Then it passes one row at a time down to find1d. Am I missing something?

hmm well basically just want to pass each array to arrayfind() from find2D function, and that'll do the searching, what you are saying is right. Everyone seems to be making entirely new functions to help search through an array but im trying to get arrayFind

int arrayFind(int A[], int n, int x)
{
for(int i = 0; i < n; i++)
if(A == x)
return i;
else
return -1;
}

to be somehow linked to find2D function where find2D function uses the original function arrayFind() and passes 1 array at a time to search for the result

[abdelhakeem]

Im trying to get arrayFind

int arrayFind(int A[], int n, int x)
{
for(int i = 0; i < n; i++)
if(A == x)
return i;
else
return -1;
}

to be somehow linked to find2D function where find2D function uses the original function arrayFind() and passes 1 array at a time to search for the result

First:
your arrayFind function is wrong because for e.g:
if you have an array of values {1, 2, 3} and you wanted to search for the number 2 which is the second element of the array, when the function begin with the first element, if it's not the wanted one the function will return -1 ignoring the other elements so your arrayFind function should look like this:

int arrayFind(int A[], int n, int x)
{
   for(int i = 0; i < n; i++)
   {
    if(A[i] == x)
     return i;
   }
   
     return -1; /* When the loop ends it means that no element matches the wanted one so the function will return -1*/
}

Second:
you have to specify the size of the second dimension of the 2D-Array in the find2D function's argument here's what you probably need:

int find2D(int Arr[][5], int rows, int ToFind)
{
    int retval;
    for (int r=0 ; r<rows ; ++r)
    {
        retval = arrayFind(Arr[r], 5, ToFind);
        if (retval>=0) return retval;
    }

    return -1;
}

If you want it to return the number of rows and the number of columns then you have to use pairs or a structure for e.g:

struct Search2D {
    int row;
    int col;
};

Search2D find2D(int Arr[][5], int rows, int ToFind)
{
    Search2D retval;
    for (int r=0 ; r<rows ; ++r)
    {
        retval.col = arrayFind(Arr[r], 5, ToFind);
        retval.row = r;
        if (retval.col>=0) return retval;
    }

    retval.row = -1;
    retval.col = -1;
    return retval;
}

[dusktreader]

You can also deduce the indices of a 2D array from a 1D iterator using modulus math:

/* Performs both integer division and modulo with improved efficiency */
void divmod( int dividend, int divisor, int &quotient, int &remainder ){
    quotient = dividend / divisor;
    remainder = dividend - divisor * quotient;
}

int find2D(int A[][], int x, int w, int h, int &i, int&j ){
    for( int idx=0; idx<n; idx++ ){
        divmod( idx, w, i, j );
        if( A[i][j] == x )
            return 1;
    }
    return -1;
}

If the function returns 1, a match was found at A[j]