2-clean-C++ implementation with detailed complexity analysis
Here is the O(M+N) solution, It is important to make it clear we choose the position\n\n         right-up-corner-position : can help us to exclude a column or a
 Here is the O(M+N) solution, It is important to make it clear we choose the position\n\n         right-up-corner-position : can help us to exclude a column or a row\n\nSo by judging the right-up-corner-value, we can exclude a column or a row one loop, so the loop is \nO(M+N) time complexity.\n\n    class Solution {\n    public:\n        bool searchMatrix(vector<vector<int>>& matrix, int target) {\n            int m=matrix.size();\n            if(m==0)  return false;\n            int n=matrix[0].size();\n            /*** start from the right-up-position ***/\n            int i=0, j=n-1;\n            while(i<m && j>=0){\n                if(matrix[i][j]==target)  return true;\n                /*** the element-of-column-j >= matrix[i][j] > target ***/\n                else if(matrix[i][j]>target)  j--;\n                /*** the element-of-row-i <= matrix[i][j] < target ***/\n                else   i++;\n            }\n            return false;\n        }\n    };\n\n\nHere is a recursion-version-implementation, by analyzing the time complexity \n\n      T(N)=3*(T(N/4)) + O(1)\n\nBased the master theory, \n\n     f(n) = O(1) = O(log(4, 3-e))    with e=2   \n\nSo\n\n     T(n) = O(N ^ log(4, 3) )    <  O(N)\n\nhere is the C++ implementation:\n\n\n       class Solution {\n        public:\n            bool searchMatrix(vector<vector<int>>& matrix, int target) {\n                if(matrix.size()==0) return false;\n                int row=matrix.size(), col=matrix[0].size();\n                return help(matrix, 0, row-1, 0, col-1, target);\n            }\n            \n            bool help(vector<vector<int>>& matrix, int row_start, int row_end, int col_start, int col_end, int target) {\n                if(row_start>row_end || col_start>col_end)  return false;\n                int row_mid=(row_start+row_end)/2, col_mid=(col_start+col_end)/2;\n                if(matrix[row_mid][col_mid]==target)    return true;\n                else if(matrix[row_mid][col_mid]>target){\n                    /*** left-up || left-down || right-up ***/\n                    return help(matrix, row_start, row_mid-1, col_start, col_mid-1, target) ||\n                        help(matrix, row_mid, row_end, col_start, col_mid-1, target) ||\n                        help(matrix, row_start, row_mid-1, col_mid, col_end, target);\n                }\n                else{\n                    /*** right-down || left-down || right-up ***/\n                    return help(matrix, row_mid+1, row_end, col_mid+1, col_end, target) ||\n                        help(matrix, row_mid+1, row_end, col_start, col_mid, target) ||\n                        help(matrix, row_start, row_mid, col_mid+1, col_end, target);\n                }\n            }\n        };
[]