C++/C# divide and conquer solution


  • 1
    O

    C++ version

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // check bad input
        int m = matrix.size();
        if(m == 0)
            return false;
        int n = matrix[0].size();
        if(n == 0)
            return false;
        return binarySearch(matrix, target, 0, m-1, 0, n-1);
    }
    
    bool binarySearch(vector<vector<int>>& matrix, int target, 
    int min_i, int max_i, 
    int min_j, int max_j){
        if(min_i > max_i)
            return false;
        if(min_j > max_j)
            return false;
        int i = (min_i + max_i)/2;
        int j = (min_j + max_j)/2;
        
        int value = matrix[i][j];
        if(value == target)
            return true;
        else if(value < target)
        {
            return binarySearch(matrix, target, min_i, max_i, j+1, max_j)
            || binarySearch(matrix, target, i+1, max_i, min_j, j);
        }
        else
        {
            return binarySearch(matrix, target, min_i, max_i, min_j, j-1)
            || binarySearch(matrix, target, min_i, i-1, j, max_j);            
        }
    }
    

    C# version

    public bool SearchMatrix(int[,] matrix, int target) {
        if(matrix == null)
            return false;
        int m = matrix.GetLength(0);
        int n = matrix.GetLength(1);
        if(n == 0 && m == 0)
            return false;
        return BinarySearch(matrix, target, 0, m-1, 0, n-1);
    }
    
    bool BinarySearch(int[,] matrix, int target, 
    int min_i, int max_i, 
    int min_j, int max_j){
        if(min_i > max_i)
            return false;
        if(min_j > max_j)
            return false;
        int i = (min_i + max_i)/2;
        int j = (min_j + max_j)/2;
        
        int value = matrix[i,j];
        if(value == target)
            return true;
        else if(value < target)
        {
            return BinarySearch(matrix, target, min_i, max_i, j+1, max_j)
            || BinarySearch(matrix, target, i+1, max_i, min_j, j);
        }
        else
        {
            return BinarySearch(matrix, target, min_i, max_i, min_j, j-1)
            || BinarySearch(matrix, target, min_i, i-1, j, max_j);            
        }
    }

Log in to reply
 

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