O(mlgn) iterative C++(12ms) and recursive C#(184ms)


  • 0
    O

    C++ iterative version

    // iterative O(mlgn) solution
    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;
        
        // Binary search each row
        for(int i = 0; i < m; ++i)
        {
          vector<int>& row = matrix[i];
          int j = 0;
          int min = 0; int max = n-1;
          // iterative process
          while(max - min >= 0)
          {
            j = (max+min)/2;
            int value = row[j];
            if(value == target)
                return true;
            else if(value < target)
                // search right value
                min = j+1;
            else
                // search left values
                max = j-1;
            }
          }
        return false;
      }
    

    C# recursive version

    // Recursive O(mlgn) solution
    public bool SearchMatrix(int[,] matrix, int target) {
        // check bad input
        if(matrix == null) 
            return false;
        int m = matrix.GetLength(0);
        int n = matrix.GetLength(1);
        if(n == 0 && m == 0)
            return false;
        
        // Binary search each row
        for(int i = 0; i < m; ++i)
        {
            if(BinarySearch(matrix, target, i, 0, n-1))
                return true;
        }
        return false;
    }
    
    bool BinarySearch(int[,] matrix, int target, int i, int min, int max)
    {
        if(min > max)
            return false;
        int j = (max+min)/2;
        int value = matrix[i,j];
        if(value == target)
            return true;
        else if(value < target)
            // search right value
            return BinarySearch(matrix, target, i, j+1, max);
        else
            // search left values
           return BinarySearch(matrix, target, i, min, j-1);
    }

Log in to reply
 

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