CareerCup

Similar to binary search.
Divide the matrix into four quarters.
Depending on how k is compared with A[n/2][m/2], k is not contained in either the upper-left or the bottom-right quarter.
So just recurse on the other 3 quarters.
The running time T(n) = 3T(n/4) + O(1), which is clearly O(log n).

Pseudocode:
Given an M * N matrix, Start from A[M][0](the bottom left corner).
If the element<k, col++;
else if the element >k, row--;
else if element==k return (i,j).

This solution is based on Youngs tableau.

find( matrix Arr , int X )
{
     int R=Arr.rowsize();
     int C=Arr.colsize();
     
     int r=R-1,c=0;
     
     while( r>=0 && c<C )
      {
          if( Arr[r][c]==X )
           {
                found ;
                print( r , c );
                return;
                
                } 
                
           else if ( Arr[r][c] > X )
             r-- ;
             
           else
            c++ ;
            
            
            }
            
            
            print( "NOT FOUND" );
            return;
            
            }

<pre lang="c" line="1" title="CodeMonkey38228" class="run-this">include <stdio.h>

int main(void) {

return 0;
}
</pre><pre title="CodeMonkey38228" input="yes">
</pre>

for each row check if the stat element is > and less than end lelement.
If the search element matches the criteria, then do a binary search on the row.
If not, move to next row.

I will be O(m long n)

Do merge sort on the two rows and do a binary search on the resultant array. this willbe O((m+n)log(m+n))

Do merge sort on the two rows and do a binary search on the resultant array. this willbe O((m+n)log(m+n))

O( logm * logn )

1. Find a row which might have a key, by looking at first column using modified binary search which will look for interval match.
2. Conventional binary search on the row returned from step 1

Please let me know for any query

Cheers
Ankush

BinarySearch2D(int inputArray[][], int m , int n, int key){
int low=0;
int high=n-1;
int mid;
do{
mid = low + (high-low)/2;
if (inputArray[mid][mid] > key){
high = mid;
} else if (inputArray[mid][mid] < key){
low = mid;
} else{
return true;
}

}while(low<high);
return BinarySearch1D(inputArray,key,mid,true) || BinarySearch1D(inputArray,key,mid,false);
}


BinarySearch1D(int inputArray[][],int key, int maxIndex, bool rowConstant){
int low=0;
int high = maxIndex-1;
do{
int mid = low + (high-low)/2;
int midValue = rowConstant ? inputArray[maxIndex][mid] : inputArray[mid][maxIndex];
if (midValue > value){
high = mid-1;
} else if (midValue < value){
low = mid+1;
} else{
return true;
}

}while(low<high);
return false;
}

BinarySearch2D(int inputArray[][], int m , int n, int key){
int low=0;
int high=n-1;
int mid;
do{
    mid = low + (high-low)/2;
    if (inputArray[mid][mid] > key){
        high = mid;
    } else if (inputArray[mid][mid] < key){
        low = mid;
    } else{
            return true;
        }
 
  }while(low<high);
return BinarySearch1D(inputArray,key,mid,true) || BinarySearch1D(inputArray,key,mid,false);
}


BinarySearch1D(int inputArray[][],int key, int maxIndex, bool rowConstant){
int low=0;
int high = maxIndex-1;
do{
    int mid = low + (high-low)/2;
        int midValue = rowConstant ? inputArray[maxIndex][mid] : inputArray[mid][maxIndex];
    if (midValue  > value){
        high = mid-1;
    } else if (midValue < value){
        low = mid+1;
    } else{
            return true;
        }
 
  }while(low<high);
return false;
}

saddleback algorithm