# Use "Divide and Conquer" to solve it

• Because the elements are in 2D matrix ascendingly, I can easily determine that target element exists upper half matrix or lower half matrix.

Time complexity:
If there is a MxN matrix, the time complexity is O(log M) + O(log N)

public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0)
return false;

return isExist(0, matrix.length - 1, target, matrix);
}

private boolean isExist(int startRow, int endRow, int target, int[][] matrix) {
if (startRow > endRow)
return false;

int middleRow = startRow + (endRow - startRow) / 2;
int lastPivot = matrix[middleRow][matrix[0].length - 1];
int startPivot = matrix[middleRow][0];

if (target == lastPivot || target == startPivot)
return true;

if (startPivot < target && target < lastPivot)
return Arrays.binarySearch(matrix[middleRow], target) >= 0;

if (target < lastPivot)
return isExist(startRow, middleRow - 1, target, matrix);
else
return isExist(middleRow + 1, endRow, target, matrix);
}

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