Binary search

Question

JackDurden 0 Junior Poster in Training

15 Years Ago

Im having trouble seeing this recursion function through. Say I have an 8 by 8 array how would I get the search function to "see" into the middle of the 8 by 8 array. Positions (4,4), (4,5),(5,4),(5,5).

#include <iostream>

using namespace std;

struct matrix
{
	int size;
	int row;
	int col;
	int newsize;
};
class tri
{
public:
	
	int expvalue(int);
	void origin(int**,int, int, int);
	void search(int**, int);
	
private:
    matrix **listPtr;
};

int tri::expvalue(int n)
{
	if(n==0)
		return 1;
	else
		return 2*expvalue(n-1);
}
void tri::origin(int** ptr, int n, int a, int b)
{
	ptr=new int*[n];

	cout<<"Origin Matrix: \n"<<endl;
	for(int i = 0; i <n; i++)
	{
		ptr[i] = new int[n];
    }
      for(int i=0;i<n;i++)
	  {
		for(int j=0;j<n;j++)
		{
			ptr[i][j]=1;//whats in the matrix
			ptr[a-1][b-1]=0;//missing square
			cout << ptr[i][j] << ' ';//display matrix
        }
		cout<<endl;
      }
}
void tri::search(int**ptr, int a)
{

	if()
		return false;
	else
	{
		int midpoint;
		midpoint=(a)/2;
		if()
			return search();
		else if()
			return true;
		else
			return search();
	}

}
void main()
{
	matrix num;
	tri print;
	int **listPtr=NULL;
	
	cout<<"Enter matrix size: ";
	cin>>num.size;
	cout<<"Enter row number: ";
	cin>>num.row;
	cout<<"Enter column number: ";
	cin>>num.col;

	num.newsize=print.expvalue(num.size);
	print.origin(listPtr, num.newsize, num.row, num.col);
	cout<<num.newsize;
	
}

c++

3 Contributors
6 Replies
65 Views
10 Hours Discussion Span
Latest Post 15 Years Ago Latest Post by skatamatic

All 6 Replies

VernonDozier 2,218 Posting Expert

15 Years Ago

Im having trouble seeing this recursion function through. Say I have an 8 by 8 array how would I get the search function to "see" into the middle of the 8 by 8 array. Positions (4,4), (4,5),(5,4),(5,5).

Don't know what you mean by "see into the middle of the array". If the array is a 2D array called ptr, then ptr[4][5] refers to the 4th row, 5th column (4, 5), ptr[5][4] refers to the 5th row, 4th column, ptr[j] refers to the ith row, jth column. What are you trying to do?

skatamatic 371 Practically a Posting Shark

15 Years Ago

Im not sure I understand the problem. What is search supposed to be returning? True if the value a is found? Are you unsure what to put in the if statements? Please be more specific.

I compiled your code and found it to be pretty broken in other places. I enter a 2 for the matrix size, and it spits out a 4x4 matrix. Is this intentional? Also, it's riddled with memory leaks.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

JackDurden 0 Junior Poster in Training · Answer 1 · 2008-10-27T05:26:59+00:00

Maybe if you run this you will get it better. I need to fill in each "box" with the three numbers. But I need to get to each box with recursion. So if I have an 8 by 8, i need to look in the middle of that, then if I have a 4 by 4, I need to look in the middle of that...and so on.

#include <iostream>

using namespace std;

struct matrix
{
	int size;
	int row;
	int col;
	int newsize;
};
class tri
{
public:
	
	int expvalue(int);
	void origin(int**,int, int, int);
	void quad(int, int**, int, int);
	void search1(int**, int);
	void search2(int**, int);
	void search3(int**, int);
	void search4(int**, int);
	
private:
    matrix **listPtr;
};

int tri::expvalue(int n)
{
	if(n==0)
		return 1;
	else
		return 2*expvalue(n-1);
}
void tri::origin(int** ptr, int n, int a, int b)
{
	ptr=new int*[n];
	

	cout<<"Origin Matrix: \n"<<endl;
	for(int i = 0; i <n; i++)
	{
		ptr[i] = new int[n];
    }
      for(int i=0;i<n;i++)
	  {
		for(int j=0;j<n;j++)
		{
			ptr[i][j]=1;//whats in the matrix
			ptr[a-1][b-1]=0;//missing square
			cout << ptr[i][j] << ' ';//display matrix
        }
		cout<<endl;
      }

	  quad( n, ptr, a, b);
	  
}
void tri::search1(int**ptr, int a)
{

		int mid;
		mid=(a)/2;
	  cout<<endl;
	  for(int i=0;i<a;i++)
	  {
		for(int j=0;j<a;j++)
		{
		ptr[mid-1][mid-1]=2;
		//ptr[mid-1][mid]=2;
		ptr[mid][mid-1]=2;
		ptr[mid][mid]=2;
		cout<<ptr[i][j]<< ' ';
        }
		cout<<endl;
      }
		
	
}
void tri::search2(int**ptr, int a)
{

		int mid;
		mid=(a)/2;
	  cout<<endl;
	  for(int i=0;i<a;i++)
	  {
		for(int j=0;j<a;j++)
		{
		//ptr[mid-1][mid-1]=2;
		ptr[mid-1][mid]=2;
		ptr[mid][mid-1]=2;
		ptr[mid][mid]=2;
		cout<<ptr[i][j]<< ' ';
        }
		cout<<endl;
      }
		
	
}
void tri::search3(int**ptr, int a)
{

		int mid;
		mid=(a)/2;
	  cout<<endl;
	  for(int i=0;i<a;i++)
	  {
		for(int j=0;j<a;j++)
		{
		ptr[mid-1][mid-1]=2;
		ptr[mid-1][mid]=2;
		//ptr[mid][mid-1]=2;
		ptr[mid][mid]=2;
		cout<<ptr[i][j]<< ' ';
        }
		cout<<endl;
      }
		
	
}
void tri::search4(int**ptr, int a)
{

		int mid;
		mid=(a)/2;
	  cout<<endl;
	  for(int i=0;i<a;i++)
	  {
		for(int j=0;j<a;j++)
		{
		ptr[mid-1][mid-1]=2;
		ptr[mid-1][mid]=2;
		ptr[mid][mid-1]=2;
		//ptr[mid][mid]=2;
		cout<<ptr[i][j]<< ' ';
        }
		cout<<endl;
      }
		
	
}
void tri::quad(int n, int **ptr, int a, int b)
{
	int t=0;
	int count=2;
	t=n/2;

	if((a<=t) && (b>=t+1))
	{
		search1(ptr, n);
	}
	if((a<=t) && (b<=t))
	{
		search2(ptr, n);
	}
	if((a>=t+1) && (b<=t))
	{
		search3(ptr, n);
	}
	if((a>=t+1) && (b>=t+1))
	{
		search4(ptr, n);
	}
}
void main()
{
	matrix num;
	tri print;
	int **listPtr=NULL;
	
	cout<<"Enter matrix size: ";
	cin>>num.size;
	cout<<"Enter row number: ";
	cin>>num.row;
	cout<<"Enter column number: ";
	cin>>num.col;

	num.newsize=print.expvalue(num.size);
	print.origin(listPtr, num.newsize, num.row, num.col);
	
}

this does it with 4 different functions but it wont do the whole thing.

skatamatic 371 Practically a Posting Shark · Answer 2 · 2008-10-27T05:48:02+00:00

So you want it to always display a 2x2 grid representing the middle? Or do you want it to display the entire middle (ie everything but the border). More descriptive variable names (or at least comments) would help also. I'm assuming that a represents the length of the matrix, which is squared to equal the total matrix size, but I am unsure if that assumption is even correct.

skatamatic 371 Practically a Posting Shark · Answer 3 · 2008-10-27T08:37:20+00:00

Well this is a working solution, it took a bit of code modifying so it might be incorrect (assuming this is an assignment for school)
I commented the things i changed

#include <iostream>

using namespace std;

struct matrix
{
	int size;
	int row;
	int col;
	int newsize;
};
class tri
{
public:
	
	int expvalue(int);
//*** now returns an int **
	int ** origin(int**,int, int, int);
//*** now accepts another int
	void search(int**, int, int);
	
private:
    matrix **listPtr;
};

int tri::expvalue(int n)
{
	if(n==0)
		return 1;
	else
		return 2*expvalue(n-1);
}
int ** tri::origin(int** ptr, int n, int a, int b)
{
	ptr=new int*[n];

	cout<<"Origin Matrix: \n"<<endl;
	for(int i = 0; i <n; i++)
	{
		ptr[i] = new int[n];
    }
      for(int i=0;i<n;i++)
	  {
		for(int j=0;j<n;j++)
		{
			ptr[i][j]=1;//whats in the matrix
			ptr[a - 1][b - 1] = 0;//missing square
			cout << ptr[i][j] << ' ';//display matrix
        }
		cout<<endl;
      }
//*** new
	  return ptr;
}
void tri::search(int**ptr, int size, int index = 0)
{
//****all new
	if (index == 0)
		index = (size / 2);
	if (index == (size / 2))
	{
		cout << ptr[index - 1][index - 1] << ptr[index - 1][index] << endl;
		search (ptr, size, index + 1);
	}
	else
		cout << ptr[index][index - 1] << ptr[index][index];

}
void main()
{
	matrix num;
	tri print;
	int **listPtr = 0;
	
	cout<<"Enter matrix size: ";
	cin>>num.size;
	cout<<"Enter row number: ";
	cin>>num.row;
	cout<<"Enter column number: ";
	cin>>num.col;
	//before listPtr wasn't being assigned to anything, so therefore couldn't be searched, so listPtr = the return int ** from origin
                
//also, you were passing in the col and row backwards
                listPtr = print.origin(listPtr, num.size, num.col, num.row);
	
//*** new
	cout << "\n\nDisplaying Middle Squares\n";
	print.search(listPtr, num.size);
	cin.ignore(cin.rdbuf()->in_avail());
	cin.get();
	
}

skatamatic 371 Practically a Posting Shark · Answer 4 · 2008-10-27T09:13:46+00:00

Note that the above code is still full of memory leaks. You should have a cleanup function run before the end of the code.

Binary search

Recommended Answers Collapse Answers

All 6 Replies

Recommended Answers