Sorted Matrix

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.

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

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

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

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

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

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

}

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

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)

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

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

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.

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

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