(My English is not good. There are some syntax errors. Several ideas wasn't written, because I don't know how to express them in English. Sorry about that.)

I will use the matrix in the problem statement as an example.

Basic idea:

**1. matrix[i][j] > matrix[k][l], where 0 ≤ i ≤ m - 1, 0 ≤ j ≤ n - 1, k ≤ i, j ≤ l, k ≠ i, l ≠ j**

Example:

1 4 711 152 5 812 193 6 916 22 10 13 14 17 24 18 21 23 26 30

Note that number 9 is the largest in the block.

Example:

1 4 7 11 152 5 8 12 193 6 9 16 2210 13 14 17 2418 21 23 26 30

Note that number 30 is the largest in the block.

**2. To Divide matrix into 4 parts, binary search within the "diagonal" a smallest number which is larger than target and is in the bottom-right part. However, if target is in it, directly return true**

The special property of the four parts will be stated soon.

Example: target = 15

"diagonal": 1 5 9 17 30

1 4 711 152 5 812 193 6 916 2210 13 14172418 21 2326 30

Number 17 is the smallest number which is larger than target in the "diagonal".

Example: target = 10

"diagonal": 1 5 9 17

1 4 711 152 5 812 193 6 916 2210 13 141724

Number 17 is the smallest number which is larger than target in the "diagonal".

Example: target = 3

"diagonal": 1 5 9 17

14 7 11258 1236 9 161013 14 171821 23 26

Number 5 is the smallest number which is larger than target in the "diagonal".

Specially, it is probably that there isn't a smallest number which is larger than target in the "diagonal". This doesn't matter.

**3.Discard the top-left part and bottom-right part, solve the remaining two parts**

Reason:

All elements in top-left sub-matrix are less than target.

All elements in bottom-right sub-matrix are larger than target.

So we needn't to search these two parts

**(Optional)4. If the matrix has only one row or only one column, we directly binary search and return true or false**

**5. Combine all sub-problems and return answer**

**Time complexity:**

Assume a matrix has N rows and N columns. In every recursion, the matrix is uniformly divided into 4 parts.

~~T(N) = 2T(N/4) + logN = N^0.5 + 2logN --> T(N) = O(N^0.5)~~

T(N) = 2T(N/2) + logN --> T(N) = O(N)

What if the matrix isn't uniformly divided into 4 parts, then we must take m into account. In this case, the problem becomes more difficult. I can't solve it.

**Here is my code:**

```
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
return dac(matrix, target, 0, 0, matrix.size() - 1, matrix[0].size() - 1);
}
private:
bool dac(const vector<vector<int>> &matrix, int target,
int x0, int y0, int x1, int y1) { // (x0, y0) and (x1, y1) denotes a searching area
int m = x1 - x0, n = y1 - y0, lo = 0, hi = min(m, n);
if (m == 0) return rowBS(matrix, target, x0, y0, y1); // If the matrix has only one row (optional)
if (n == 0) return colBS(matrix, target, y0, x0, x1); // If the matrix has only one column (optional)
while (lo <= hi) { // binary search the smallest value which is greater than target in the "diagonal"
int mid = lo + (hi - lo) / 2, x = x0 + mid, y = y0 + mid;
if (matrix[x][y] < target) lo = mid + 1;
else if (matrix[x][y] > target) hi = mid - 1;
else return true;
}
if (hi == -1) return false; // The bottom-right sub-matrix is really the current matrix,
// those elements are all greater than target
return lo <= m && dac(matrix, target, x0 + lo, y0, x1, y0 + lo - 1) // search bottom-left part
|| lo <= n && dac(matrix, target, x0, y0 + lo, x0 + lo - 1, y1); // search top-right part
// needn't to search the top-left sub-matrix as well as the bottom-right sub-matrix,
// because all elements in them are either greater than target or smaller than target
}
bool rowBS(const vector<vector<int>> &matrix, int target, int x, int lo, int hi) {
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (matrix[x][mid] < target) lo = mid + 1;
else if (matrix[x][mid] > target) hi = mid - 1;
else return true;
}
return false;
}
bool colBS(const vector<vector<int>> &matrix, int target, int y, int lo, int hi) {
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (matrix[mid][y] < target) lo = mid + 1;
else if (matrix[mid][y] > target) hi = mid - 1;
else return true;
}
return false;
}
};
```