Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:

1
2
3
4
5
6
7
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Solution

这个矩阵的特点是，对于任意的 x = matrix[i,j]， 左上部分（红色）的值均小于x, 右下部分（青色）的值均大于x，而左下、右上部分（灰色）和x的大小关系则完全未知。

Matrix

所以一个简单的思路即从矩阵右上角或者左下角开始，逐渐向对角方向（并不一定严格对角）走，并不断排除所在位置左上、右下部分从而达到比较高的效率。时间复杂度为O(m+n)

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean searchMatrix(int[][] matrix, int target) {
   	int r = matrix.length; 
    if(r < 1)
       return false;
    int c = matrix[0].length;
        
    int i = 0, j = c-1;
    while(i < r && j >= 0){
       	if(matrix[i][j] == target)
          	return true;
       	else if(matrix[i][j]  < target)
          	i++;
       	else
  			j--;
   }
   return false;
}

python 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
	# @param {integer[][]} matrix
	# @param {integer} target
	# @return {boolean}
	def searchMatrix(self, matrix, target):
		y = len(matrix[0]) - 1
		for x in range(len(matrix)):
			while y and matrix[x][y] > target:
				y -= 1
			if matrix[x][y] == target:
				return True
		return False

另外一种思路即tag中提到的二分查找和分治的思想，每次取矩阵中心x，然后将矩阵分割为左上、左下、右上、右下四个部分，如何 target大于x， 则舍弃左上部分，如果小于x ， 则舍弃右下部分。

时间复杂度 \(T(n) = 3\times T(n/2)+c\)

java代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class Solution {
	public boolean searchMatrix(int[][] matrix, int target) {
     
        int r = matrix.length; 
        if(r < 1)
            return false;
        int c = matrix[0].length;
        
        return helpFunc(0,0,r-1,c-1,matrix,target);
    }
    
    //divide the matrix into 4 parts and then recursive call
    //start point and end point
    private Boolean helpFunc(int sx, int sy, int ex, int ey, int[][]m, int t){
        if(t < m[sx][sy] || t > m[ex][ey])
            return false;
        
        if(sx < ex || sy < ey){
            //middle point
            int mx = (ex-sx)/2+sx;
            int my = (ey-sy)/2+sy;
            
            boolean ret = false;
            if(my < ey)
                ret = ret || helpFunc(sx,my+1,mx,ey,m,t);
            if(mx < ex)
                ret = ret || helpFunc(mx+1,sy,ex,my,m,t);
            
            if(m[mx][my] > t)
                return helpFunc(sx,sy,mx,my,m,t)||ret;
            else if(m[mx][my]<t){
                if(mx< ex && my < ey)
                    return helpFunc(mx+1,my+1,ex,ey,m,t)||ret;
                else
                    return ret;
            }else
                return true;
        }else
            return m[sx][sy] == t;
    }
}