# AC Java solution with divide and conquer(Follow the hide tags)

• BST is a nice method, I was write another method following the hide tags.

``````public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
if(target < matrix[0][0]) return false;
if(target > matrix[m - 1][n - 1]) return false;
return searchMatrixHelper(matrix, target, 0, 0);
}

private static boolean searchMatrixHelper(int[][] matrix, int target, int i,
int j) {
int m = matrix.length;
if(i >= m) return false;
int n = matrix[0].length;

while(matrix[i][n - 1] < target) i++;
return searchMatrixHelper(matrix, target, i + 1, j)||searchInRow(matrix, target, i, j);
}

private static boolean searchInRow(int[][] matrix, int target, int i, int j) {
int n = matrix[0].length;
int start = j;
int end = n - 1;

while(start <= end){
int mid = (start + end)/2;
if(target == matrix[i][mid]) return true;
if(target > matrix[i][mid]) start = mid + 1;
else end = mid - 1;
}
return false;
}
``````

}

• Nice solution. I think the time complexity here is O(mlogn).
It is very similar to follow up of lc162 find peak element that to find peak element in a 2D matrix.

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