开始在你的矩阵的左下角。然后往右走，直到找到确切的数目（完成），或者直到你找到一个数字，这是更大的。

然后你在矩阵中去向上，直到找到确切的数目（完成），或者直到你找到一个数字，这是太小了。

然后再移动到右侧，......依此类推，直到你找到的号码或直到你到达右侧的矩阵或顶部。

下面的图像包含了一些例子，使用Excel表格显示为绿色的目标数量，以及随后在黄色的道路。

在我们寻找207的最后一个例子，这是不是在矩阵：

这仅仅是算法。编码是留给你作为练习： - ）

编辑：：当在最后一行开始，二进制搜索可能会给一个更好的起点。对于该算法它可能并不重要的其余部分。

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

}

Start in the bottom-left corner of your matrix. Then go to the right until you find the exact number (done), or until you find a number that is bigger.

Then you go upwards in the matrix until you find the exact number (done), or until you find a number that is too small.

Then again you move to the right, ... and so on until you found the number or until you reach the right-side or top of your matrix.

The following images contain some examples, using an Excel table showing the target number in green, and the path that is followed in yellow.

In the last example we look for 207, which isn't in the matrix:

This is just the algorithm. The coding is left for you as an exercise :-)

EDIT: When starting on the bottom row, a binary search might give a better starting point. For the rest of the algorithm it probably doesn't matter.