題目：
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 程序員人生 版權所有
