# Is this binary search O(log m + log n) ?

• ``````int min(int a, int b) {
return a < b? a : b;
}

bool searchx(int **m, int y, int x1, int x2, int t) {
int count = x2 - x1, step;
int x;
if (count <= 0) return false;
while (count>0) {
step = count / 2;
x = x1 + step;
if (m[x][y] < t) {
x1 = x + 1;
count -= step+1;
} else {
count=step;
}
}
return x1 != x2 && m[x1][y] == t;
}

bool searchy(int **m, int x, int y1, int y2, int t) {
int count = y2 - y1, step;
int y;
if (count <= 0) return false;
while (count>0) {
step = count / 2;
y = y1 + step;
if (m[x][y] < t) {
y1 = y + 1;
count -= step+1;
} else {
count=step;
}
}
return y1 != y2 && m[x][y1] == t;
}

bool searchxy(int **m, int x1, int y1, int x2, int y2, int t) {
int count = min(x2 - x1, y2 - y1), step;
if (count <= 0) return false;
if (x2 - x1 == 1) return searchy(m, x1, y1, y2, t);
if (y2 - y1 == 1) return searchx(m, y1, x1, x2, t);
int x3 = x1, y3 = y1;
int x, y;
while (count>0) {
step = count / 2;
x = x3 + step, y = y3 + step;
if (m[x][y] < t) {
x3 = x + 1;
y3 = y + 1;
count -= step+1;
} else {
count=step;
}
}
if (x3 < x2 && y3 < y2 && m[x3][y3] == t) return true;
if (searchxy(m, x1, y3, x3, y2, t) || searchxy(m, x3, y1, x2, y3, t)) return true;
return false;
}

bool searchMatrix(int** matrix, int matrixRowSize, int matrixColSize, int target) {
return searchxy(matrix, 0, 0, matrixRowSize, matrixColSize, target);
}``````

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