Search a 2D matrix


  • -3
    B

    For this problem, we need to search if an element is in the matrix. I know there is a good method to find the element in O(m + n) complexity. (search an element from top right element) My code is as followed:

    public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            // Note: The Solution object is instantiated only once and is reused by each test case.
            for(int i = 0, j = matrix[0].length - 1; i < matrix.length && j >= 0;){
                if(matrix[i][j] == target)
                    return true;
                else if(matrix[i][j] < target)
                    i++;
                else
                    j--;
            }
            return false;
        }
    }
    

    However, I still think this is not a very regular method to do that? Are there any other more conventional way to solve this problem?


  • 0
    S

    Could you please format the code? The last } is out of the code box.


  • 0
    S

    Your code assumes the matrix is sorted. If so, for large matrices it might be better do binary search (look at the matrix as an array of MxN elements - O(log(MxN)) complexity


  • 30
    B

    Here is the code that used binary search.
    The matrix can be viewed as a one-dimensional sorted array. The value of element i in this array in the matrix is matrix[i/cols][i%cols].

    public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            // Start typing your Java solution below
            // DO NOT write main() function
            int rows = matrix.length;
            int cols = matrix[0].length;
            
            int s = 0, e = rows* cols - 1;
            while(s<=e){
                int m = s+(e-s)/2;
                if(matrix[m/cols][m%cols]==target)
                return true;
                else if(matrix[m/cols][m%cols]>target){
                    e = m -1;
                }else{
                    s = m + 1;
                }
            }
            return false;
        }
    }

  • 6
    U

    Actually, you can solve this problem by 2-pass binary search, which is in O(log m + log n)


  • 0
    L

    That's really neat. So much nicer than coding two binary search!


  • 0
    S
    This post is deleted!

  • 0

    Note: to users who might be confused:
    The problem @baojialiang described is this: Searching a 2D sorted matrix, which had not been added to OJ yet.

    The answers below are based on the OJ problem Search a 2D matrix, which is similar, but has an added restriction:

    The first integer of each row is greater than the last integer of the previous row.

    Therefore, the solution @baojialing described works, but is not efficient enough compared to the binary search solution mentioned by @beijingyangbo.


  • 0
    G

    We can do much faster than O(log(MxN)). We would need only O(log m + log n) as described below :)


  • 0
    M

    O(log(m*n)) and O(log m + log n) they are mathematically equal...


  • 0
    G

    My apologies, I don't know why I made such a comment!


  • 0
    M

    yes, first do a binary search on the coloum[0] -> find the row (by using lower_bound type fuction)
    then do a binary search on the found row, return true or false.

    I think it is correct....if any flaw...plz comment it.


  • 0
    F

    I think we should also consider the case where rows* cols is too large for an int. When it is small matrix, this works awesome.


  • 0
    W

    the operator / &% may cost lots of time...


  • 0
    R

    You mean this?
    My solution is exactly matching your description.

    class Solution {

    public:

    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        
        auto end_it = upper_bound(matrix.cbegin(),
                                  matrix.cend(),
                                  target,
                                  by_first_element);
        if (end_it == matrix.cbegin()) return false;
        
        for (auto row_it = matrix.cbegin();
             row_it != end_it;
             ++row_it)
        {
            auto cell_it = lower_bound(row_it->cbegin(),
                                       row_it->cend(),
                                       target);
            if (cell_it == row_it->cend()) continue;
            if (*cell_it == target) return true;
        }
    
        return false;        
    }
    
    static bool by_first_element(const int& b, const vector<int>& a)
    {
        return b < a.front();
    }
    

    };


  • 0
    R

    The matrix is not sorted. Rows are sorted, first element for each row is sorted. One single binary search on the entire matrix is wrong.


  • 0
    R

    The matrix content is not sorted. Read the text.
    Each row is sorted.
    The first column is sorted.
    Not the whole matrix.

    You can do two binary searches.


  • 0
    R

    O(m + n) is not the best solution.
    You can perform binary search for the first column, and than bynary search for each row with the firs value <= of target.


  • 0
    L

    read the description again yo not only you are the smartest ass.


  • 0
    S

    this is my code. I use twice binary search to seek the target. First search the rows, then the cols
    It's log(m)+log(n)

    class Solution {
    public:
    	bool searchMatrix(vector<vector<int> > &matrix, int target) {
    		int matrixRows = matrix.size();
    		int matrixCols = matrix[0].size();
    		if(matrixRows == 0)
    			return false;
    		if(matrixRows == 1)
    			return findCol(matrix[0], 0, matrix[0].size()-1, target);
    
    		if(target<matrix[0][0] || target > matrix[matrixRows-1][matrixCols-1])
    			return false;
    		if(target > matrix[matrixRows-1][0]) //if the target in the last row
    			return findCol(matrix[matrixRows-1], 0, matrixCols-1, target);
    
    		vector<int> rowFirstElement;
    		int idx=0;
    		while(idx<matrixRows)
    		{
    			rowFirstElement.push_back(matrix[idx][0]);
    			idx++;
    		}
    
    		int row = findRow(rowFirstElement, 0,  matrixRows-1, target);
    		if(row < 0 )
    			return false;
    		else
    			return findCol(matrix[row], 0, matrixCols-1, target);
    
    	}
    
    	int findRow(vector<int> &vec, int low, int high, int target)
    	{
    		int length = high - low;
    		if(length == 0)
    			return low;
    		if(length == 1)
    		{
    			if(vec[high] > target)
    				return low;
    			else
    				return high;
    		}
    
    		if(vec[low+length/2] > target)
    			findRow(vec, low, low+length/2-1, target);
    		else
    			findRow(vec, low+length/2, high, target);
    	}
    
    	bool findCol(vector<int> &vec, int low, int high, int target)
    	{
    		int length = high - low;
    		if(length == 0)
    			return target == vec[low];
    		if(length == 1)
    			return target == vec[low] || target == vec[high];
    
    		if(vec[low+length/2] == target)
    			return true;
    		else if(vec[length/2] > target)
    			findCol(vec, low, low+length/2-1, target);
    		else
    			findCol(vec, low+length/2, high, target);
    	}
    };

Log in to reply
 

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