# Determine if an element exists in a sorted NxN matrix

The point of this algorithm is to see if an element exists in a NxN matrix that has its rows and columns sorted.

What would you change? What did I do well? Both perspectives help so I am not left guessing.

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <algorithm>
/* Author: Matthew Everett Hoggan                                           */
/* Date: August 8, 2011                                                     */
/* Problem Statement:                                                       */
/* Given an matrix such that every row is sorted and every column is sorted */
/* write a function "find_kth_element_and_return_rowXcol" that returns a    */
/* a pair<int,int> where the element was found. If it is not found return   */
/* <N,N> to indicate to user that their value was not found                 */

namespace Matrix
{
/* This class is designed to solve the problem at hand                  */
/* The method definitions are described where they are defined          */
/* Note this matrix is a N x N square matrix                            */
class RandomOrderedMatrix
{
public:
RandomOrderedMatrix( int N );
~RandomOrderedMatrix( );
void find_element( int element );
void print_matrix( );
std::pair<int,int>& get_coord( ) { return this->data; }
private:
void build_matrix( );
int **matrix;
std::pair<int,int> data;
int N;
friend std::ostream& operator<< ( std::ostream &out, Matrix::RandomOrderedMatrix &rom )
{
std::pair<int,int> d = rom.data;
return out << "<" << d.first << ", " << d.second << ">" << std::endl;
}
};

/* ctor                                                                 */
RandomOrderedMatrix::RandomOrderedMatrix( int N )
{
this->N = N;
this->matrix = new int*[N];
for( int r=0;r<N;r++ ) matrix[r] = new int[N];
this->build_matrix( );
}

/* dtor                                                                  */
RandomOrderedMatrix::~RandomOrderedMatrix( )
{
if( matrix )
{
for( int r=0;r<N;r++ ) delete [ ] matrix[r];
delete [ ] matrix;
}
}

/* This is the n lg(n) algorithm required to find the coord of an elem.  */
/* Assuming that the rows and columns are all sorted we find the row     */
/* with the right range matrix[row][0] <= element <= matrix[row][N]      */
/* Once it finds the right row if it existis it performs binary search   */
/* which is lg(n) to see if element exists on that row. If the element   */
/* is found it prints sets the coordinate pair member variable to the    */
/* row and column where it found it. If it did not find the elment it    */
/* sets the member variable coordinate pair to N                         */
void RandomOrderedMatrix::find_element( int element )
{
int left_index = 0;
int right_index = N-1;
/* Scan the rows */
for( int r = 0; r < N; r++ )
{
/* Check the range for that row */
if( element >= matrix[r][0] && element <= matrix[r][N-1] )
{
/* Binary search */
while( right_index>left_index ) {
int middle = (right_index+left_index)/2;
if( element == matrix[r][middle] )
{
data.first = r;
data.second = middle;
return;
}
else if( element > matrix[r][middle] )
{
left_index = middle + 1;
}
else if( element < matrix[r][middle] )
{
right_index = middle - 1;
}
}
}
/* These last two cases are used when there are only two items   */
/* left in the binary partition                                  */
if( element == matrix[r][left_index] )
{
data.first = r;
data.second = left_index;
return;
}
if( element == matrix[r][right_index] )
{
data.first = r;
data.second = right_index;
return;
}
}
/* If function above did not find the elements then set them to N to */
/* notify the client that their pair could not be found              */
data.first = N;
data.second = N;
}

/* Pretty Formating Print functino =)                                    */
void RandomOrderedMatrix::print_matrix( )
{
std::cout << "Your Matrix is" << std::endl;
std::cout << std::setw( 6 ) << " ";
std::cout << std::setw( 6 ) << " ";
for( int c=0;c<N;c++ )
{
std::cout << std::setw( 6 ) << c;
}
std::cout << std::endl;
for( int r=0;r<N;r++ )
{
std::cout << std::setw( 6 ) << r;
std::cout << std::setw( 6 ) << "|";
for( int c=0;c<N;c++ )
{
std::cout << std::setw( 6 ) << matrix[r][c];
}
std::cout << std::setw( 6 ) << "|";
std::cout << std::endl;
}
}

/* Build a matrix such that the rows are sorted and the columns are      */
/* sorted.                                                               */
void RandomOrderedMatrix::build_matrix( )
{
matrix[0][0] = rand( )%50;
for( int c=1; c<N; c++ ) matrix[0][c] = matrix[0][c-1] + rand( )%50;
for( int r=1; r<N; r++ )
{
for( int c=0; c<N; c++ )
{
if( c == 0 )
{
matrix[r][c] = matrix[r-1][N-1]+rand( )%50;
}
else
{
matrix[r][c] = matrix[r][c-1]+rand( )%50;
}
}
}
}
}

/* Driver function, normally found in another file, but to facilitate        */
/* reading I have included it here                                           */
/* I also included some unit testing code which automates the testing        */
/* If you want you can uncomment it to make your testing easier              */
int main( int argc, char *argv[ ] )
{
Matrix::RandomOrderedMatrix rom( 10 );
rom.print_matrix( );
srand((unsigned)time(NULL));
int element;
std::cout << "Please input a number to find in your matrix>>> ";
while( std::cin >> element )
{
rom.find_element( element );
std::pair<int,int> &results = rom.get_coord( );
if( results.first != 10 && results.second != 10 )
{
std::cout << "Results success, found " << element << " @ coord " << rom;
}
else
{
std::cout << "Results failed could not find " << element << " in matrix " << std::endl;
}
std::cout << "Please input a number to find in your matrix>>> ";
}
/* Slight Unit Testing
for( int x = 0; x < 20; x++ )
{
std::cout << "%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%" << std::endl;
int element = rand( )%10000;
rom.find_element( element );
std::pair<int,int> &results = rom.get_coord( );
if( results.first != 10 && results.second != 10 )
{
std::cout << "Results success, found " << element << " @ coord " << rom;
}
else
{
std::cout << "Results failed could not find " << element << " in matrix " << std::endl;
}
std::cout << "%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%" << std::endl;
}
//*/
}


I would replace:

        int **matrix;


with:

        std::vector<std::vector<int> >  matrix; /* or Boost::Matrix */


RandomOrderedMatrix::RandomOrderedMatrix( int N )
: matrix(N, std::vector<int>(N))

// , N(N)   Don't need this anymore size is part of the vector
{
build_matrix( );
}

/* dtor                                                                  */
// Don't need the de-structor


This also solves the problem of not obeying the "rule of three".

Move this:

srand((unsigned)time(NULL));


To the first line of main() (note your build matrix uses rand() which is happening before the call to srand() thus you are not getting random numbers).

• I just finished reading C++ Programming Language (Special Edition) but don't recall seeing anything about the "rule of three" . Wikipedia (en.wikipedia.org/wiki/Rule_of_three_(C%2B%2B_programming)) was helpful, and I can recall context where such things were discussed. Where does this exact phrase come from? – Matthew Hoggan Aug 10 '11 at 8:44
• I have a suspicion it's from Herb Sutter GoTW series, but I can't find a link right now. – Flexo Aug 10 '11 at 12:40
• It comes from. If you need to write a special version of any destructor/assignment operator/copy constructor then you will probably need to write all three. Personally I think it is a silly name I prefer the rule of four (though nobody else uses it) because the compiler generates four methods automatically for you and if you have a RAW owned pointer in your class you will need to override all four (though I believe there are more now in C++0x with move). So we may be seeing a re-name soon. – Martin York Aug 10 '11 at 15:13
• The "Rule of Three++0x" ?... – paercebal Aug 13 '11 at 19:12