本题要求在一个形如：
[ [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]]的矩阵中查找一个特定值，矩阵每行和每列都是有序的。 看到这一题，一个直接的想法就是二分查找，本题中的矩阵有序，可以仿照二分查找中的方法写一个四分查找，但仔细想的话，如果使用四分查找，并不能想二分那样每次都将问题缩小一半，虽然说本题很容易确定目标是否在一个矩阵中，这样的做法一定是有意义的，但很难确定其复杂度，比如，如果在这个矩阵中找15，则只能确定15不在左上的子矩阵中，另外3个子矩阵还是要一一查找的，所以这并不是很有把握的一种方法，最差的情况可能会很糟。 其实如果直接用二分查找的话，复杂度反而很容易计算，如果对每行进行二分查找（也可以对每列，但是实现比较麻烦），要进行m次二分查找，每次查找的复杂度是logn，所以总体的复杂度就是O(mlogn)，这样的复杂度还是不错的，实现代码也相当简单：
#include <iostream>#include <vector>#include <algorithm>using namespace std;class Solution {public: bool searchMatrix(vector<vector<int> >& matrix, int target) { for (unsigned int i = 0; i < matrix.size(); i++) { if (matrix[i].empty()) return false; if (binary_search(matrix[i].begin(), matrix[i].end(), target)) return true; } return false; }};新闻热点
疑难解答
