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


  • -2
    T
    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);
    }

Log in to reply
 

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