Problem: Given a matrix in which each row and each column is sorted, write a method to find an element in it.
It is a classic interview question, here is my solution
boolean F(int[][] matrix, int hs, int he, int ws, int we)
{
if (hs > he || ws > we)
return false;
int m = (hs + he) / 2;
int n = (ws + we) / 2;
if (matrix[m][n] == t)
{
return true;
}
else if (matrix[m][n] < t)
{
// find the ele in the same row, right to [m][n]
F(m, m, n + 1, we);
// find the ele in the same col, upper to [m][n]
F(m + 1, he, n, n);
// find the ele in the area, where i>m,j>n
F(m + 1, he, n + 1, we);
}
else if (matrix[m][n] > t)
{
// very similar to previous part
}
}
The running time of the algorithm is log(m) + log(n). I am looking for an algorithm that is more efficient, or with concise code.
Having more comments, I come up with following code:
// return target recurrence in the matrix
int F(int[][] m, int rs, int re, int cs, int ce, int t){
int r1 = rs, r2 = re;
int c1 = cs, c2 = ce;
int r=0 , c = c1;
while( r1 < r2 && c1 < c2 ){
// find the last element that <= t in column c
r = FlastLess( r1, r2, c, t)
if( r == -1 ) break;
else{
// find the first ele in the row that is >=t
c = FfirstGreater( r, c1, c2, t);
if( c == -1) break;
else{
r2 = r;
c1 = c;
}// else
}// else
}// while
}// f
Here is the link to function F1 and F2 Find the first element in a sorted array that is greater than the target
void FlastLess(int s, int e, int t){
int l = s, h = e;
while( l != h ){
int mid = (l+h)/2;
if( mid >= t) high = mid - 1;
else {
if( high < t) low= mid + 1;
else low = mid;
}
}
void FfirstGreater(int s, int e, int t){
while(l < h){
mid = (l+h)/2;
if ( mid <= t) low = mid+1;
else high = mid;
}
}
}
