Sorted Matrix

You are given a matrix. The matrix elements are such that they are sorted both horizontally and vertically. Given an element of the matrix, your job is to obtain its position in an efficient manner.
Example:
10 20 30
15 35 98
48 76 110
Input: 76
Output: 3rd row, 2nd column.

Questions by hari_nowayout   answers by hari_nowayout

Showing Answers 1 - 15 of 15 Answers

rem132

  • Sep 2nd, 2008
 

Start at upper right corner and go in each step down or left depending of the result of comparison of current element and the element we search.

10 20 30
15 35 98
48 76 110
Input: 76
Output: 3rd row, 2nd column.

First start from extreme right-top and keep on seraching until you reach extreme left-down.

      n=0; m=0;

      while(n<3 && m<3){
          if(array[n][m]<desired){
              if(m>=2){
                 cout<<"Move Down :: ";
                 m = 2;
                 n++;
                 cout<<array[n][m]<<endl;
                 std::cin.get();
              }
              else{
                 if(array[n][m+1]>desired){
                    cout<<"Move Down :: ";
                    n++;
                    cout<<array[n][m]<<endl;
                    std::cin.get();
                 }
                 else{
                    cout<<"Move Left :: ";
                    m++;
                    cout<<array[n][m]<<endl;
                    std::cin.get();
                 }
              }
          }
          else
          if(array[n][m]>desired){
              if(m>=2){
                  m = 2;
              }
              cout<<"Move Right :: ";
              m--;
              cout<<array[n][m]<<endl;
              std::cin.get();
          }
          else{
              cout<<"FOUND:: "<<n+1<<" row, "<<m+1<<" column :: "<<array[n][m]<<endl;
              break;
          }
      }

  Was this answer useful?  Yes

aks3937

  • Jan 15th, 2009
 

in this Question our need is to find an element effeciently ,so i suggest one logic that can be implemented here are in 2 ways ... 1ST HORIZONTAL :->compare  1st and last element of every row with searching element and if the element lies in between the row , then search the element in that row or else go to next row until last row ..... similarly we can apply in VERTICAL way also......

logik

  • Apr 3rd, 2009
 

Check this one....

int SearchInArray( int **Arr, int Lower, int Upper)

{
 int middle = ( Lower + Upper )/2;
 int row     = middle/COL;
 int col       = middle%COL;

 if( Arr[row][col] == NumberToSearch )
  return middle;
 if( NumberToSearch < Arr[row][col] )
  return SearchInArray( Arr, Lower, middle - 1); 
 else return SearchInArray( Arr, middle + 1, Upper);
}

  Was this answer useful?  Yes

sabapc

  • Jul 12th, 2009
 

I'm assuming the matrix is NxM (not necessarily square) and there are no duplicate values (otherwise the search should return multiple results).

So that said, you can do the following:
1) go to the "center" of the matrix (dividing it in 4 quadrants)
2) if the value we're searching is smaller than the value at the center
      => we can discart the lower-right quadrant
      => we do recursive search on the other 3 quadrants
    if the value we're searching is greater than the value at the center
      => we can discart the upper-left quadrant
      => we do recursive search on the other 3 quadrants

// usage of the function
int[] result = find(value, matrix, 0, 0, N-1, M-1);

int[] find(int value, int[][] matrix, int i1, int j1, int i2, int j2) {
    if(i2<i1 || j2<j1)
        return null;
    if(i1==i2)
        return binary_search on row i1
    if(j1==j2)
        return binary_search on col j1

    // we go to the center of the matrix
    int i = (i1+i2)/2;
    int j = (j1+j2)/2;
    int midval = matrix[i][j];
    if(value==midval) {
        int[] solution = {i, j};
        return solution;
    }
    else if(value < midval) {
        // we discart lower-right quadrant
        int[] upleft = find(value, matrix, i1, j1, i-1, j-1);
        int[] upright = find(value, matrix, i1, j+1, i-1, j2);
        int[] lowleft = find(value, matrix, i+1, j1, i2, j-1);
        return upleft if(upleft != null);
        return upright if(upright != null);
        return lowleft if(lowleft != null);
        return null; // nothing found
    }
    else { // (value > midval)
        // we discart upper-left quadrant
        int[] upright = find(value, matrix, i1, j+1, i-1, j2);
        int[] lowleft = find(value, matrix, i+1, j1, i2, j-1);
        int[] lowright = find(value, matrix, i+1, j+1, i2, j2);
        return upright if(upright != null);
        return lowleft if(lowleft != null);
        return lowright if(lowright != null);
        return null; // nothing found
    }
}

I think that should do it.

About the order... you always reduce the solution space to 3/4, so the order should be logaritmic, but with a base smaller than 2, i.e. instead of something like log_2(n), it would be something like log_[1.33](n). This is clearly not a demonstration, just intuition.

complexity: O(LINE+COL)

class point
{
int x; int Y;
public:
point():x(-1),y(-1){}//constractor
setPoint(int x,intY){this->x=x;this->y=y;}
}

point SortedMatrix( int A[LINE][COL], int m)
{
int i=0,j=0;
point p = new point();
while(i<LINE) && (j<COL))
      {
         if(A[i][j]==m) {p.setPoint(i,j);return p;}
         if(A[i][j+1]==m) {p.setPoint(i,j+1);return p;}
         else if(A[i][j+1]<m) j++;
         if(A[i+1][j]==m) {p.setPoint(i+1,j);return p;}
         else if(A[i+1][j]<m) i++;
      }
return p;
}

#include

<iostream>

using

namespace std;

const

int max_size=50;

int

static x=0;

int

find(int matrix[max_size][max_size],int i,int j,int num)

{

while(num<matrix[x][j])

j--;

if(num==matrix[x][j])

{

cout<<

"found att"<<x<<","<<j<<"n";

return 0;

}

while (num<matrix[i][x])

i--;

if(num==matrix[i][x])

{

cout<<

"found att"<<i<<","<<x<<"n";

return 0;

}

x++;

if(x>i||x>j)

{

cout<<

"cannot find the numbern";

return -1;

}

return find(matrix,i,j,num);

}

int

main()

{

int matrix[max_size][max_size];

matrix[0][0] =34;

for(int i = 0;i<max_size;i++)

{

int r = rand();

if(i==0)

matrix[i][0]= r;

else

matrix[i][0] = matrix[i-1][0]+r;

for(int j=1;j<max_size;j++)

{

int r = rand();

matrix[i][j]=matrix[i][j-1]+r;

}

}

int

num =0;

cin>>num;

find(matrix,max_size,max_size,num);

}

  Was this answer useful?  Yes

anonymous

  • Jul 15th, 2011
 

Code
  1. #include<stdio.h>

  2. #include<stdlib.h>

  3.  

  4. int** take_input(int **input , int n )

  5. {

  6.  int i , j ;

  7.  input = (int **)malloc((sizeof(int *))*n) ;

  8.  

  9.  for( i =0 ; i< n ; i++)

  10.    input[i] = ( int *) malloc( (sizeof(int))*n ) ;

  11.  

  12.  for(i = 0 ; i <n ; i++)

  13.   {

  14.    for( j =0 ; j< n ; j++)

  15.     {

  16. printf("enter the numbers in the sorted matrix

  17. Please enter such that the rows and columns are sorted

  18. Due to time constraint the check has not been given

  19. ");

  20.         scanf("%d", &input[i][j]);

  21.         printf("%d      ", input[i][j]);

  22.     }

  23.   }

  24.  return input ;

  25. }

  26.  

  27. void display( int **input , int n)

  28. {

  29. int i , j ;

  30.  printf("

  31. the entered matrix is :::

  32. ");

  33.  for(i = 0 ; i<n ; i++)

  34.  {

  35.   for( j= 0 ; j<n ; j++)

  36.   {

  37.     printf("%d  ", input[i][j]);

  38.   }

  39.   printf("

  40. ");

  41.  }

  42. }

  43.  

  44. void locate(int **input , int n )

  45. {

  46.  int index , col , row ,check=0, i ,j , k, l , ref_col, ref_row;

  47.  

  48.  printf("enter the value which needs to be located

  49. ");

  50.  scanf("%d", &index);

  51.  

  52.  ref_col = 0;

  53.  ref_row = 0;

  54.  

  55. while(1)

  56.  {

  57.   if( input[ref_row][ref_col]< index )

  58.    {

  59.         if((ref_row==n-1) && (ref_col== n-1))

  60.         {

  61.                 printf("the value is not present

  62. ");

  63.                 break ;

  64.         }

  65.         else if((ref_col==n-1))

  66.         {

  67.          ref_row+=1;   

  68.         }

  69.         else if(check == 0)

  70.          ref_col+=1;

  71.         else

  72.           ref_row+=1;

  73.        

  74.         check = 0;

  75.    }

  76.   else if(input[ref_row][ref_col]>index)

  77.   {

  78.         if(ref_col==0)

  79.         {

  80.                 printf("The value entered could not be located

  81. ");

  82.                 break ;

  83.         }

  84.         else

  85.          ref_col-=1;

  86.         check = 1;

  87.   }

  88.  

  89.  else

  90.  {

  91.   printf("the location of the index value has been located at %dth row and %dth column

  92. ", (ref_row+1), (ref_col+1));

  93.   break ;

  94.  }

  95.  }

  96.  

  97. }

  98.  

  99. int main()

  100. {

  101.  

  102.  int **input ;

  103.  int i ,  dimen ;

  104.  printf("enter the dimensions of the sqaure matrix

  105. ");

  106.  scanf("%d",&dimen);

  107.  input =take_input(input, dimen);

  108.  display(input, dimen);

  109.  do{

  110.   locate( input , dimen );

  111.  printf("do you want to locate more numbers ???

  112. 1.Yes

  113. 2.No

  114. ");

  115.  scanf("%d",&i);

  116. }while(i==1);

  117.  

  118. }

  119.  

  Was this answer useful?  Yes

Jitendra Chittoda

  • Sep 4th, 2011
 

Start with the bottom left most corner and keep on checking the value.

# If the serchable item is greater then the item present in bottom most corner then it is confirmed that the item is present in this row only, then continue searching in same row until you find the item.
# else if the serchable item is less then the item present in bottom most corner then move up one and continue this process.

So the worst case complexity is O(m+n)

  Was this answer useful?  Yes

micheal

  • Sep 16th, 2011
 

Assume the matrix is M X N ,m=index for row and n=index for column, compare the last element(N-1) in each row wherever you find the first element bigger than the value you break out of the loop and then apply bsearch to the array a[m][N] where n =1 to n

Code
  1. #include<stdio.h>

  2. #include<conio.h>

  3. #define M 50

  4. #define N 50

  5. void main()

  6. {

  7. int a[M][N],m,n,row,col,value;

  8. clrscr();


  9.  ENTER THE ROW AND COLUMNS OF THE MATRIX");

  10. scanf("%d",&row);

  11. scanf("%d",&col);

  12. printf("ENTER THE VALUE OF THE MATRIX");

  13. for(m=0;m<row;m++)

  14. for(n=0;n<col;n++)

  15. scanf("%d",&a[m][n]);

  16. printf("

  17.  ENTER THE VALUE TO BE SEARCHED");

  18. scanf("%d",&value);

  19. for(m=0;m<row;m++)

  20. {

  21.   if(a[m][col-1]>=value)

  22.   break;

  23.  

  24. }

  25. n=col-1

  26. while(1)

  27. {

  28.   if(a[m][n]==value)

  29. {

  30. printf("%d

  31. %d",m,n);

  32. break;

  33. }

  34. else

  35.   if(a[m][n]>value)

  36.  {

  37.     n=n/2;

  38. }

  39. else

  40. if(a[m][n]<value)

  41. {

  42. n++;

  43. }

  44. }

  45. getch();

  46. }

  Was this answer useful?  Yes

raquelle

  • May 9th, 2012
 

I dont think you have to compare one from the other.. as I understand the problem.. what you have to do is to find the number in the matrix and know its location.. since the matrix is fix,. it is best to put it in a 2 dimensional array.. like matrix[x][y].. where x represents the row and y for the column.. by using for{} loop inside another for{} loop.. you can search for the inputted number and print x and y for position..

  Was this answer useful?  Yes

taruchu

  • Feb 10th, 2013
 

The algorithm will consist of a binary search on each column or on each row of the 2d matrix. By noting which column or row position you are doing the search on gives you the first index location in the 2d matrix. The second index is the exact location returned by the binary search in that column or row.

  Was this answer useful?  Yes

sandy

  • Mar 24th, 2013
 

I assume you can do it in the following way:

Code
  1. class Coordinate:

  2.     def __init__(self,x=0,y=0):

  3.         self.x = x

  4.         self.y = y

  5.  

  6. def findElement(a,n):

  7.     if a == None:

  8.         return Coordinate(-1,-1)

  9.    

  10.     bl_y = len(a) - 1

  11.     bl_x = 0

  12.     i,j = bl_x,bl_y

  13.    

  14.     while  j >= 0 and i < len(a[i]) :

  15.         row = a[j]

  16.        

  17.         ##Look at the row

  18.         while i < len(a[0]) and row[i] <= n:

  19.             if row[i] == n:

  20.                 return Coordinate(i,j)

  21.             i = i + 1

  22.         if i > 0:

  23.             i = i - 1

  24.         j = j - 1

  25.     return Coordinate(-1,-1)

  26.  

  27. if __name__ == __main__:

  28.     a = [

  29.          [10,20,30],

  30.          [15,35,98],

  31.          [48,76,110]

  32.         ]

  33.     c = findElement(a,111)

  34.     print (str(c.x) + " "+str(c.y))

  Was this answer useful?  Yes

Give your answer:

If you think the above answer is not correct, Please select a reason and add your answer below.

 

Related Answered Questions

 

Related Open Questions