Total Accepted: 43629 Total Submissions: 138231
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
Given target = 3, return true.
常规思路, 多次二分
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty())
return false;
vector<int> firstCol;
for(auto v : matrix)
firstCol.push_back(v[0]);
if(binary_search(firstCol.begin(), firstCol.end(), target))
return true;
vector<int>::iterator iter = lower_bound(firstCol.begin(), firstCol.end(), target);
int low = iter - firstCol.begin();
for(int i = 0; i < low; i++)
{
if(binary_search(matrix[i].begin(), matrix[i].end(), target))
return true;
}
return false;
}
投机取巧,存在潜在的bug
bool searchMatrix(vector<vector<int> >& matrix, int target) {
int rows = matrix.size();
if (rows == 0) return false;
int cols = matrix[0].size();
int first = 0, last = rows * cols - 1;
if (target < matrix[0][0] || target > matrix[rows - 1][cols - 1])
return false;
int mid, val;
// binary search
while (first <= last) {
mid = first + (last - first) / 2;
val = matrix[mid / cols][mid % cols];
if (val > target)
last = mid - 1;
else if (val == target)
return true;
else
first = mid + 1;
}
return false;
}
原文：http://www.cnblogs.com/ydlme/p/4589402.html