### 题目

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,   4,  7, 11, 15],
[2,   5,  8, 12, 19],
[3,   6,  9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]


Given target = 5, return true.

Given target = 20, return false.

### DFS

• 如果x > target，就要么往 “左” 走，要么往 “上” 走。
• 如果x < target，就要么往 “右” 走，要么往 “下” 走。
• 如果x = target，就找到目标数。

• time: $O(n\log_{}{n})$
• space: $O(n)$

#### 代码

public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0) { return false; }
int height = matrix.length, width = matrix[0].length;
int halfHeight = (height - 1) / 2;
int halfWidth = (width - 1) / 2;
boolean[][] visited = new boolean[height][width];
return dfs(matrix,target,halfHeight,halfWidth,visited);
}
private boolean dfs(int[][] matrix, int target, int x, int y, boolean[][] visited) {
if (x < 0 || x == matrix.length || y < 0 || y == matrix[0].length || visited[x][y]) { return false; }
int val = matrix[x][y];
visited[x][y] = true;
if (val > target) {
return dfs(matrix,target,x-1,y,visited) || dfs(matrix,target,x,y-1,visited);
} else if (val < target) {
return dfs(matrix,target,x+1,y,visited) || dfs(matrix,target,x,y+1,visited);
} else {
return true;
}
}
}


### 二分查找

target = 5

[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]


target = 5

[1,   4,  7, 11, 15]
[2,   5,  8, 12, 19]

"5" insert here
|
[3,   6,  9, 16, 22] <- 中位行

[10, 13, 14, 17, 24]
[18, 21, 23, 26, 30]


target = 5

淘汰（都太小）                   保留递归
[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]
保留递归                    淘汰（都太大）


• time: $O(\log_{}{n})$
• space: $O(1)$

#### 代码

/** Binary Search */
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0) { return false; }
return binarySearch(matrix,target,0,matrix.length-1,0,matrix[0].length-1);
}
private boolean binarySearch(int[][] matrix, int target, int up, int down, int left, int right) {
if (up > down || left > right) { return false; }
int mid = up + (down - up) / 2;
int index = index(matrix,target,mid,left,right);
if (index != matrix[0].length && (matrix[mid][index] == target)) {
return true;
} else {
return binarySearch(matrix,target,mid+1,down,left,index-1) || binarySearch(matrix,target,up,mid-1,index,right);
}
}
/** find the index to insert the target number */
private int index(int[][] matrix, int target, int row, int lo, int hi) {
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int val = matrix[row][mid];
if (val > target) {
hi = mid - 1;
} else if (val < target) {
lo = mid + 1;
} else {
return mid;
}
}
return lo;
}
}