题目
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true
示例 2:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false
思路
按题目所说，数组从左到右，从上到下都是有序排列的，那么我们可以通过下标映射关系将二维数组转化为逻辑上的一维数组，这个以为数组是从小到大有序排列的，所以就可直接采用经典的二分搜索，具体代码如下：
代码
class Solution {
public boolean searchMatrix(int[][] matrix
, int target
) {
int m
= matrix
.length
, n
= 0;
if (m
> 0)
n
= matrix
[0].length
;
int left
= 0, right
= m
*n
-1;
while (left
<= right
){
int mid
= (left
+right
)/2, midVal
= matrix
[mid
/n
][mid
%n
];
if (midVal
< target
)
left
= mid
+1;
else if (midVal
> target
)
right
= mid
-1;
else
return true;
}
return false;
}
}
