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
.
问题:在给定的已排序的二维矩阵中,判断是否包含某个整数。
思路:看到二维数组,首先想到的是二维数组和 一维数组可以直接转换,arr[i][j] 等于 arr[i*col + j]。而在一个已排序的一维数组中搜索一个元素,可以采用分治(Divide and Conquer)思想,更具体些就是二分搜索(Binary Search) 算法。
将上面的结合起来就是,先实现一维数组的二分搜索算法,然后将算法中的一位转换为二维数组即可。
bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.size() == ) {
return false;
} int col = (int)matrix[].size();
int row = (int)matrix.size(); if (col == && row == ) {
return ( matrix[][] == target );
} int lm = ;
int rm = col * row - ; while (lm < rm ) { if (lm + == rm) {
int quoL = lm / col;
int remL = lm % col; int quoR = rm / col;
int remR = rm % col; if (matrix[quoL][remL] == target || matrix[quoR][remR] == target) {
return true;
}else{
return false;
}
} int midm = (lm + rm) / ; int quo = midm / col;
int rem = midm % col; if (matrix[quo][rem] == target) {
return true;
} if (matrix[quo][rem] < target) {
lm = midm;
}else{
rm = midm;
}
} return false;
}