A log(mn) solution, get passed 66/127 cases, but get stuck in a very simple case


  • -3
    W

    this code works perfectly in my computer, and passes 66/127 cases. But the code fails when encountering [[-5]], -5. Will someone there figure it out?

    #define GET_OFF(off, r, c, rsize) ((off) + ((r) * (rsize)) + (c))
    #define GET(m, off, r, c, rsize)                                               \
           *((int *)(((void *)(m)) + GET_OFF(off, r, c, rsize) * sizeof(int)))
    void binarySearch(int** matrix, int startOffset, int rowSize, int colSize, 
        int target, int matrixRowSize);
    static bool result = false;
    bool searchMatrix(int** matrix, int matrixRowSize, int matrixColSize, 
        int target) {
        //binary search
        binarySearch(matrix, 0, matrixRowSize, matrixColSize, target, 
               matrixRowSize);
        return result;
    }
    
    void binarySearch(int** matrix, int startOffset, int rowSize, int colSize, 
          int target, int matrixRowSize) {
            
        int rowHalf = rowSize/2, colHalf = colSize/2;
        int currInt;
        if(result)
            return;
        currInt = GET(matrix, startOffset, rowHalf, colHalf, matrixRowSize);
        if(currInt == target) {
            result = true;
            return;
        }
        else if(rowSize == 0 || colSize == 0 || (rowSize == 1 && colSize == 1))
            return;
        else if(currInt < target)
            //search bottom right
            binarySearch(matrix, GET_OFF(startOffset, rowHalf + 1, colHalf + 1, 
                matrixRowSize), rowSize - rowHalf - 1, colSize - colHalf -1, target,
                matrixRowSize);
        else
            //search top left
            binarySearch(matrix, GET_OFF(startOffset, 0, 0, matrixRowSize), 
                rowHalf, colHalf, target, matrixRowSize);
        //search bottom left
        binarySearch(matrix, GET_OFF(startOffset, rowHalf + 1, 0, 
             matrixRowSize), rowSize - rowHalf - 1, colHalf + 1, target, 
             matrixRowSize);
        //search top right
        binarySearch(matrix, GET_OFF(startOffset, 0, colHalf + 1, 
              matrixRowSize), rowHalf + 1, colSize - colHalf - 1, target, 
              matrixRowSize);
    }

Log in to reply
 

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