# Another easy-to-understand recursive solution with simple explanation !

• `````` target = 21

[
[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]
]
1. Search in the most right column

15
19
22-->start, top
24
30

2. Search in the row [3,   6,   9,   16,   22]
|
startR, right
3. Search in the sub matrix
[
[3,  6,   9,  16],
[10, 13,  14, 17],
[18, 21,  23, 26]
]
``````

""

``````public boolean searchMatrix(int[][] matrix, int target) {
int right = matrix[0].length-1;
int top = 0;

return findRecursive(matrix, target, right, top);
}

private boolean findRecursive(int[][] matrix, int target, int right, int top){
if(top==matrix.length) return false;
if(right<0) return false;

int start = top;
int end = matrix.length-1;
//Search in the most right column
while(start<=end){
int mid = start + (end-start)/2;
if(target == matrix[mid][right]) return true;
else if(target < matrix[mid][right]) end = mid-1;
else start = mid+1;
}

top = start;
if(top==matrix.length) return false;

int startR = 0;
int endR = right;
//Search in one row
while(startR<=endR){
int midR = startR + (end - start)/2;
if(target == matrix[top][midR]) return true;
else if(target < matrix[top][midR]) endR = midR - 1;
else startR = midR+1;
}

return findRecursive(matrix, target, endR, top+1);
}
``````

""

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.