题目：
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列肯定给定数字可能存在哪1行，然后利用2分法在该行进行搜索。
C++参考代码：
class Solution
{
public:
bool searchMatrix(vector<vector<int> > &matrix, int target)
{
int rows = int(matrix.size());
int row = 0;
bool flag = false;//标志是不是有某1行的第1个数字比给定的数字大
for (int i = 0; i < rows; ++i)
{
if (matrix[i][0] == target) return true;
if (matrix[i][0] > target)
{
row = i;
flag = true;
break;
}
}
//这里是对特殊情况的处理：如果每行的第1个数字都比给定数字小，那末说明给定数字有可能在最后1行
//如果falg=true而且row=1，说明第1行的第1个数字比给定数字大，那末矩阵中肯定不存在给定数字，直接返回false
if (flag && row == 0) return false;
else if (!flag) row = rows;
//下面是对矩阵第row - 1行进行2分查找的进程
int left = 0;
int right = int(matrix[row - 1].size()) - 1;
int middle = right / 2;
while (left <= right)
{
middle = (left + right) / 2;
if (matrix[row - 1][middle] > target) right = middle - 1;
else if (matrix[row - 1][middle] < target) left = middle + 1;
else return true;
}
return false;
}
};
程序员人生，我编程，我富裕，记住wfuyu网，php教程，php学习，php手册，CMS模版制作
声明：本站大部分内容是作者原创，少部分收集于互联网供大家一起学习，原版权很多不明，如有侵权请联系本站，谢谢！
粤ICP备14040726号-1 2015-2020 程序员人生 版权所有
