My Code:

```
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int r=matrix.size();
if(r==0) return false;
int c=matrix[0].size();
if(c==0) return false;
return subsrh(matrix,target,0,0,r-1,c-1);
}
private:
bool subsrh(vector<vector<int>>& matrix, int target, int x1, int y1, int x2, int y2){
if(x1>x2||y1>y2||target<matrix[x1][y1]||target>matrix[x2][y2]) return false;
if(x2-x1<=1&&y2-y1<=1)
return target==matrix[x2][y2]||target==matrix[x1][y1]||target==matrix[x2][y1]||target==matrix[x1][y2];
int m1=(x1+x2)/2, m2=(y1+y2)/2;
if(matrix[m1][m2]==target) return true;
else if(matrix[m1][m2]>target)
return subsrh(matrix, target, x1, y1, m1-1, y2)||subsrh(matrix, target, m1, y1, x2,m2-1);
else {
return subsrh(matrix, target, x1, m2+1, x2, y2)||subsrh(matrix, target, m1+1, y1, x2, m2);
}
}
};
```

Time complexity? I can't solve this T(MN)=T(MN/2)+T(MN/4)+O(1).

Updates: Thanks to @StefanPochmann

T(MN) ≈ Θ((MN)^0.694),