1.问题描写叙述
写一个高效的算法。从一个m×n的整数矩阵中查找出给定的值，矩阵具有例如以下特点：
每一行从左到右递增。
每一列从上到下递增。
2. 方法与思路
2.1 二分查找法
依据矩阵的特征非常easy想到二分法，可是这是一个二维的矩阵，怎样将问题转化为一维是关键。实际上我们能够依据矩阵的第一列确定值可能所在的行的范围(limu,limd)，当中limu=0，使得matrix[0][0]≤matrix[i][0]≤matrix[limd][0]，i∈[0,limd]。
而确定limd的值能够使用二分法。
确定了值可能在的行的范围后。逐行在进行二分查找目标值。这样就将问题降到一维上来了。代码例如以下：
class Solution {
public:
bool searchMatrix(vector<vector<int> >& matrix, int target) {
if(matrix.size() == 0) return false;
int i,j,mid,rows = matrix.size(),cols = matrix[0].size();
int limd = rows-1,limu = 0;
/*二分查找目标值可能所在行的下限*/
while(limu < limd)
{
mid = (limu + limd)/2;
if(matrix[mid][0] > target) limd = mid - 1;
else if(matrix[mid][0] < target) limu = mid +1;
else return true;
}
/*对每一行进行二分查找*/
for(i = 0; i <= limd; i++)
{
int l = 0, r = cols-1;
while(l <= r)
{
mid = (l + r)/2;
if(matrix[i][mid] < target) l = mid+1;
else if(matrix[i][mid] > target) r = mid - 1;
else return true;
}
}
return false;
}
};2.2 分治法
另一种方法就是採用分值的思想。以题目给出矩阵为例，查找数字5。细致观察矩阵，最右上角的数字为15，因为矩阵是列递增，所以数字5不可能在最右側15这一列，我们便可将这一列不予考虑，将范围缩减了一列。
[1, 4, 7, 11]
[2, 5, 8, 12]
[3, 6, 9, 16]
[10, 13, 14, 17]
[18, 21, 23, 26]
再推断数字11。相同11>5，又缩减一列。数字７相同小于５，在缩减一列。那么如今的矩阵变为：
[1, 4,]
[2, 5]
[3, 6]
[10, 13]
[18, 21]
推断数字４时，因为5>4，目标值肯定不在4所在的行，去点这一行，在进行推断。
[2, 5]
[3, 6]
[10, 13]
[18, 21]
Okay，推断数字5，找到目标值返回。
这样的算法时间复杂度O(n),要优于第一种算法。代买例如以下：
class Solution {
public:
bool searchMatrix(vector<vector<int> >& matrix, int target) {
if(matrix.size() == 0) return false;
int i,j,rows = matrix.size(),cols = matrix[0].size();
i = 0;
j = cols-1;
while(i < rows && j >= 0)
{
if(matrix[i][j] == target) return true;
else if(matrix[i][j] > target) j--;
else i++;
}
return false;
}
};