Description
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 in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,
Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 5, return true.
Given target = 20, return false.
Explain
這道題題意就是給一個每行都是從左到右排好序的擂仍，每列也是從上到下排好序的矩陣。然后給一個值，詢問這個值是否在矩陣?yán)锩婧碜谩Ｎㄒ挥行畔⒕褪菑淖蟮接液蛷纳系较率桥藕眯虻摹Ｕf明每行的第一個值只要比目標(biāo)值大泵喘，那么這一行就可以忽略不計了泪电。它后面的行也是。那么我們可以先確定一個行的范圍纪铺。確定行的范圍后相速，由于這個值有可能出現(xiàn)在任一行。我們可以枚舉每一可行行鲜锚，然后二分查找突诬。
Code
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty()) return false;
if (matrix[0].empty()) return false;
int start = 0;
for (start = 0; start < matrix.size(); start++) {
if (matrix[start][0] > target) break;
}
bool res = false;
helper(matrix, 0, start == matrix.size() ? start - 1 : start, res, target);
return res;
}
void helper(vector<vector<int>>& matrix, int left, int right, bool& res, int target) {
if (res) return;
if (left > right) return;
int mid = (right - left) / 2 + left;
int _left = 0, _right = matrix[mid].size() - 1;
while(_left <= _right) {
int _mid = (_right - _left) / 2 + _left;
if (matrix[mid][_mid] > target) _right = _mid - 1;
else if (matrix[mid][_mid] < target) _left = _mid + 1;
else {
res = true;
return;
}
}
helper(matrix, left, mid - 1, res, target);
helper(matrix, mid + 1, right, res, target);
}
};
