題目：
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列肯定給定數(shù)字可能存在哪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個數(shù)字比給定的數(shù)字大
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個數(shù)字都比給定數(shù)字小，那末說明給定數(shù)字有可能在最后1行
//如果falg=true而且row=1，說明第1行的第1個數(shù)字比給定數(shù)字大，那末矩陣中肯定不存在給定數(shù)字，直接返回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網(wǎng)，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學習，原版權很多不明，如有侵權請聯(lián)系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
