rem132

 Profile Answers by 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.

raniela

 Profile Answers by raniela 

• Sep 8th, 2008

 

1. run Binary search on first column (i=0)
2. run Binary search on the chosen row. O(logn)

TriVinDreamer

 Profile Answers by TriVinDreamer 

• Oct 24th, 2008

 

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;
          }
      }

aks3937

 Profile Answers by 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

 Profile Answers by 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);
}

sabapc

 Profile Answers by 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.

Asher The King

 Profile Answers by Asher The King 

• Jul 10th, 2011

 

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;
}

Vishesh Bibhay

 Profile Answers by Vishesh Bibhay 

• Jul 11th, 2011

 

#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);

}

anonymous

• Jul 15th, 2011

 

Code
#include<stdio.h>


#include<stdlib.h>


 


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


{


 int i , j ;


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


 


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


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


 


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


  {


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


    {


printf("enter the numbers in the sorted matrix 


 Please enter such that the rows and columns are sorted 


 Due to time constraint the check has not been given


");


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


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


    }


  }


 return input ; 


}


 


void display( int **input , int n)


{


int i , j ;


 printf("


 the entered matrix is ::: 


");


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


 {


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


  {


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


  }


  printf("


");


 }


}


 


void locate(int **input , int n )


{


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


 


 printf("enter the value which needs to be located 


");


 scanf("%d", &index);


 


 ref_col = 0;


 ref_row = 0;


 


while(1)


 {


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


   {


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


        {


                printf("the value is not present 


");


                break ;


        }


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


        {


         ref_row+=1;    


        }


        else if(check == 0)


         ref_col+=1;


        else 


          ref_row+=1;


        


        check = 0;


   }


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


  {


        if(ref_col==0)


        {


                printf("The value entered could not be located


");


                break ;


        }


        else


         ref_col-=1;


        check = 1; 


  }


 


 else


 { 


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


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


  break ;


 }


 }


 


}


 


int main()


{


 


 int **input ;


 int i ,  dimen ; 


 printf("enter the dimensions of the sqaure matrix 


");


 scanf("%d",&dimen);


 input =take_input(input, dimen);


 display(input, dimen);


 do{


  locate( input , dimen );


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


1.Yes


2.No


");


 scanf("%d",&i);


}while(i==1);


 


}


 

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)

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
#include<stdio.h>


#include<conio.h>


#define M 50


#define N 50


void main()


{


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


clrscr();


printf(


 ENTER THE ROW AND COLUMNS OF THE MATRIX");


scanf("%d",&row);


scanf("%d",&col);


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


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


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


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


printf("


 ENTER THE VALUE TO BE SEARCHED");


scanf("%d",&value);


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


{


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


   break;


 


}


n=col-1


while(1)


{


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


 {


printf("%d


%d",m,n);


break;


}


else


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


  {


     n=n/2;


} 


else


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


{


n++;


}


}


getch();


}

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..

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.

frogInSea

 Profile Answers by frogInSea 

• Mar 14th, 2013

 

I think it can be solved in a two dimensional Binary-Search way

sandy

• Mar 24th, 2013

 

I assume you can do it in the following way:

Code
class Coordinate:


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


        self.x = x


        self.y = y


 


def findElement(a,n):


    if a == None:


        return Coordinate(-1,-1)


    


    bl_y = len(a) - 1


    bl_x = 0


    i,j = bl_x,bl_y


    


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


        row = a[j]


        


        ##Look at the row


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


            if row[i] == n:


                return Coordinate(i,j)


            i = i + 1


        if i > 0:


            i = i - 1


        j = j - 1


    return Coordinate(-1,-1)


 


if __name__ == __main__:


    a = [


         [10,20,30],


         [15,35,98],


         [48,76,110]


        ]


    c = findElement(a,111)


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