# Two java solutons. O(log(m+n)) is better than O(log(m) + log(n))

• The best solution must be binary search. So at first I use two bi-searchs to find row_id and col _id. The time complexity is O(log(m) + log(n)). While if we take the matrix as a sorted array, one bi-search is enough. And the tiem complexity is O(log(m+n)).
The two solutions are below:

``````public boolean searchMatrix(int[][] matrix, int target) {
int col_id = 0;
int rlen = matrix.length;
int clen = matrix[0].length;
int row_id = row_search(matrix, target, 0, rlen-1, clen);
//System.out.println(row_id);
if (matrix[row_id][clen-1] < target){
row_id += 1;
}
//System.out.println(row_id);
if (row_id >= matrix.length)
return false;

col_id = col_search(matrix, target, 0, clen-1, row_id);
//System.out.println(col_id);
if(matrix[row_id][col_id] != target)
return false;
return true;
}

public int row_search(int[][] matrix, int target, int begin, int end, int clen){
if(begin >= end)
return begin;
int mid = (begin + end) / 2;
if (matrix[mid][clen-1] == target)
return mid;
else if(matrix[mid][clen-1] < target){
return row_search(matrix, target, mid + 1, end, clen);
}
else
return row_search(matrix, target, begin, mid - 1, clen);
}

public int col_search(int[][] matrix, int target, int begin, int end, int row_id){
if(begin >= end)
return begin;
int mid = (begin + end) / 2;
if (matrix[row_id][mid] == target)
return mid;
else if(matrix[row_id][mid] < target){
return col_search(matrix, target, mid + 1, end, row_id);
}
else
return col_search(matrix, target, begin, mid - 1, row_id);
}

//this is the second solution.
public boolean searchMatrix2(int[][] matrix, int target){
if(matrix.length == 0)
return false;
int start = 0;
int row = matrix.length, col = matrix[0].length;
int end = row * col - 1;
while(start <= end){
int mid = (start + end) / 2;
if(matrix[mid/col][mid%col] == target){
return true;
}
else if(matrix[mid/col][mid%col] < target){
start = mid + 1;
}
else{
end = mid - 1;
}
}
return false;
}``````

• Why is the second solution O(log(m+n))? It's like doing binary search on a sorted array of length mn so the time complexity is O(log(mn)) = O(log(m) + log(n)).

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