3 different Binary Search Solutions and 1 O(M+N)


  • 0
    L

    [1] Quad Search Solution: the idea is to get the middle index and split the matrix to 4 parts, divide and conquer.

    public bool SearchMatrix(int[,] matrix, int target) {
        return quadSearch(matrix, 0, 0, matrix.GetLength(0) - 1, matrix.GetLength(1) - 1, target);
    }
    private bool quadSearch(int[,] matrix, int x1, int y1, int x2, int y2, int target)
    {
        if(x1 >= matrix.GetLength(0) || y1 >= matrix.GetLength(1) || target > matrix[x2, y2] || target < matrix[x1, y1])
            return false;
        if(x1 == x2 && y1 == y2)
            if(matrix[x1, y1] == target) return true;
            else return false;
        int midX = (x1 + x2) >> 1, midY = (y1 + y2) >>1;
        if(matrix[midX, midY] == target) return true;
        else if(matrix[midX, midY] > target)
            return quadSearch(matrix,       x1,       y1, midX, midY, target) ||
                   quadSearch(matrix, midX + 1,       y1,   x2, midY, target) ||
                   quadSearch(matrix,       x1, midY + 1, midX,   y2, target);
        else
            return quadSearch(matrix, midX + 1,       y1,   x2, midY, target) ||
                   quadSearch(matrix,       x1, midY + 1, midX,   y2, target) ||
                   quadSearch(matrix, midX + 1, midY + 1,   x2,   y2, target);
    }
    

    [2] O(Log(M)+Log(N)) Iterative Solution: the idea is to b-search the up/down/left/right boundaries and do the b-search in each smaller matrix repeatedly. The worst case is O(M+N). 408ms

    public bool SearchMatrix(int[,] matrix, int target) {
        int m = matrix.GetLength(0), n = matrix.GetLength(1);
        int x1 = 0, y1 = 0, x2 = m - 1, y2 = n - 1;
        while (m != 1 || n != 1)
        {
            //1) B-Search to Get Up and Down boundaries
            int iUp = x1, iDown = x2, iUpBoundary, iDownBoundary;
            while (iUp <= iDown){
                int mid = (iUp + iDown) >> 1;
                if (matrix[mid, y2] > target) iDown = mid - 1;
                else if (matrix[mid, y2] < target) iUp = mid + 1;
                else if (matrix[mid, y2] == target) return true;
            }
            if (n == 1) return false;
            iUpBoundary = iUp; iUp = x1; iDown = x2;
            while (iUp <= iDown){
                int mid = (iUp + iDown) >> 1;
                if (matrix[mid, y1] > target) iDown = mid - 1;
                else if (matrix[mid, y1] < target) iUp = mid + 1;
                else if (matrix[mid, y1] == target) return true;
            }
            if (iUpBoundary > (iDownBoundary = iDown)) return false;
            //2) B-Search to Get Left and Right boundaries
            int iLeft = y1, iRight = y2, iLeftBoundary, iRightBoundary;
            while (iLeft <= iRight){
                int mid = (iLeft + iRight) >> 1;
                if (matrix[iDownBoundary, mid] > target) iRight = mid - 1;
                else if (matrix[iDownBoundary, mid] < target) iLeft = mid + 1;
                else if (matrix[iDownBoundary, mid] == target) return true;
            }
            if (m == 1) return false;
            iLeftBoundary = iLeft; iLeft = y1; iRight = y2;
            while (iLeft <= iRight){
                int mid = (iLeft + iRight) >> 1;
                if (matrix[iUpBoundary, mid] > target) iRight = mid - 1;
                else if (matrix[iUpBoundary, mid] < target) iLeft = mid + 1;
                else if (matrix[iUpBoundary, mid] == target) return true;
            }
            if (iLeftBoundary > (iRightBoundary = iRight)) return false;
            x1 = iUpBoundary; y1 = iLeftBoundary;
            x2 = iDownBoundary; y2 = iRightBoundary;
            m = x2 - x1 + 1; n = y2 - y1 + 1;
        }
        return (m == 1 && n == 1 && matrix[x1, y1] == target) ? true : false;
    }
    

    [3] O(M*LogN) Solution: First, b-search row upper boundary, then b-search row down boundary, finally b-search each rows in the range of boundaries.

    public bool SearchMatrix(int[,] matrix, int target) {
        int m = matrix.GetLength(0), n = matrix.GetLength(1), iUp = 0, iDown = m - 1, iDownBoundary, iUpBoundary;
        while(iUp < iDown){
            int mid = (iUp + iDown) >> 1;
            if(matrix[mid, n - 1] > target) iDown = mid;
            else if(matrix[mid, n - 1] < target) iUp = mid + 1;
            else if(matrix[mid, n - 1] == target) return true;
        }
        iDownBoundary = iDown; iUp = 0; iDown = m - 1;
        while(iUp <= iDown){
            int mid = (iUp + iDown) >> 1;
            if(matrix[mid, 0] > target) iDown = mid - 1;
            else if(matrix[mid, 0] < target) iUp = mid + 1;
            else if(matrix[mid, 0] == target) return true;
        }
        iUpBoundary = iDown; //  iDownBoundary <= iUpboundary 
        for(int i = iDownBoundary; i <= iUpBoundary; i++){
            int iLeft = 0, iRight = n - 1;
            while(iLeft <= iRight){
                int mid = (iLeft + iRight) >> 1;
                if(matrix[i, mid] > target) iRight = mid - 1;
                else if(matrix[i, mid] < target) iLeft = mid + 1;
                else if(matrix[i, mid] == target) return true;
            }
        }
        return false;
    }
    

    [4] O(M+N) 412ms

    public bool SearchMatrix(int[,] matrix, int target) {
        for(int i = matrix.GetLength(0) - 1, j = 0; i >= 0 && j < matrix.GetLength(1);)
            if(matrix[i, j] > target) i--;
            else if (matrix[i, j] < target) j++;
            else return true;
        return false;
    }

  • 0
    S

    hi
    what is the time complexity of your first Quad Search Solution ?

    Thanks


  • 0
    L

    Scott, it's
    T(n, = 3 [ 3T(n ] + c = 3 [ 3 [ 3T(n/8) + c ] + c ] + c = 3kk(3k - 1)/2 = 3k k) = 3lg n(3lg nlg 3) <== 3lg nlg 3 = O(n1.58)


  • 0

    @scott I think it is O(3^log4(MN)). T(MN) = 3T(1/4 * MN) + O(1)


Log in to reply
 

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