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 from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.
【题目分析】
给定一个矩阵，满足矩阵中每一行都是递增的，而且每一行的第一个值比上一行的最后一个值要大，在这个矩阵中找到一个目标值。
【思路】
1. 最坏时间复杂度为O(m+n)的方法
分析矩阵我们发现矩阵有一个特点：它的每一行是递增的，而且每一列也是递增的。我们从矩阵的坐下角出发，如果目标值比当前值大，列索引就加1，如果目标值比当前值小，那么横索引就加1，直到搜索到目标值或者搜索完整个矩阵。例如我们要从如下矩阵中寻找目标值9：
<-----这个矩阵的每一行的第一个数并不比上一行最后一个数大，但是这个算法依旧可以应用在本题目。
我们从18出发，绿色线条显示了我们的移动轨迹。可以很容易看出，如果目标值为右上角的元素，则需要搜索最长的步数。
2. 时间复杂度为log(m) + log(n)的算法
很明显我们可以采用二分查找算法查找第一列，定位出目标值位于哪一行，然后在该行再采用二分查找具体确定目标值的位置。
【思路1代码】
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null) return false;
int i = matrix.length - 1;
int j = 0;
while(i >= 0 && j < matrix[0].length){
if(target > matrix[i][j]) j++;
else if(target < matrix[i][j]) i--;
else return true;
}
return false;
}
}