# My AC Solution, divide and conquer. Feel this solution is better than O(m+n), T(n) = lgn + 2T(n/2)

• Use binary search we find the break point and discard upper left and bottom right area.

``````public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length==0 || matrix[0][0]>target) return false;
return helper(matrix, target, 0, matrix.length-1, 0, matrix[0].length-1);
}
public boolean helper(int[][] matrix, int target, int xstart, int xend, int ystart, int yend) {
if(xstart>xend || ystart>yend) return false;
int xs = xstart, xe = xend, ys = ystart, ye = yend;
while(xs<xe || ys<ye) {
int xm = xs + (xe-xs)/2, ym = ys + (ye-ys)/2;
if(matrix[xm][ym]==target) return true;
else if(matrix[xm][ym]<target) {
xs = (xs==xe? xs: xm+1);
ys = (ys==ye? ys: ym+1);
} else {
xe = xm;
ye = ym;
}
}
if(matrix[xs][ys]==target) return true;
return helper(matrix, target, xs, xend, ystart, ys-1) ||
helper(matrix, target, xstart, xs-1, ys, yend);
}``````

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