# What is the complexity of this solution? Binary search on four edges. My answer is in average log(m)*log(m), assuming m > n; worst case m*log(m)

• ``````    public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0) return false;
return helpSearch(matrix, target, 0, 0, matrix.length-1, matrix[0].length-1);
}
private boolean helpSearch(int[][] matrix, int target, int r1, int c1, int r2, int c2) {
if (r1 > r2 || c1 > c2) return false;
if (r1 == r2 && c1 == c2) return matrix[r1][c1] == target;
int l = r1;
int r = r2;
while (l < r) {
int mid = (l+r+1)/2;
if (matrix[mid][c1] == target) return true;
if (matrix[mid][c1] < target) l = mid;
else r = mid-1;
}
r2 = r;

l = c1;
r = c2;
while (l < r) {
int mid = (l+r+1)/2;
if (matrix[r1][mid] == target) return true;
if (matrix[r1][mid] < target) l = mid;
else r = mid-1;
}
c2 = r;

l = r1;
r = r2;
while (l < r) {
int mid = (l+r)/2;
if (matrix[mid][c2] == target) return true;
if (matrix[mid][c2] < target) l = mid+1;
else r = mid;
}
r1 = l;

l = c1;
r = c2;
while (l < r) {
int mid = (l+r)/2;
if (matrix[r2][mid] == target) return true;
if (matrix[r2][mid] < target) l = mid+1;
else r = mid;
}
c1 = l;
return helpSearch(matrix, target, r1, c1, r2, c2);
}
``````

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