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.
假设直接对矩阵元素进行二分查找的话，时间复杂度是O(m*n)，事实上非常easy想到先通过查找找到相应可能存在于哪一行，然后再在那行中查找是否存在，採用最简单的直接查找这样时间复杂度仅有O(m+n)，假设这两次查找再分别採用二分查找的话，时间复杂度更能够减少到O（logm+logn），以下是O（m+n）的代码：
class Solution { public: bool searchMatrix(vector<vector<int> > &matrix, int target) { if(matrix.empty()) return false; int m = matrix.size(); int n = matrix[0].size(); int i = 0, j=0; while(i<m && target>=matrix[i][0]) i++; i--; if(i==-1) return false; while(j<n) { if(target == matrix[i][j]) return true; else j++; } return false; } };
转载于:https://www.cnblogs.com/bhlsheji/p/4270151.html
