Search A 2D Matrix Problem Solution

Search A 2D Matrix Problem: Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Search A 2D Matrix Problem Solution

Problem Solution In Python

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False

        row = []
        # store the row with great or equal value to the target
        for record in matrix:
            if record[-1] >= target:
                row = record
                break
        
        # iterate through the row until you find the target
        for element in row[::-1]:
            if element == target:
                return True

        return False

Problem Solution In Java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {

        //corner case
        if(matrix == null || matrix.length == 0) return false;
        if(matrix[0] == null || matrix[0].length == 0) return false;

        int r = matrix.length;
        int c = matrix[0].length;

        int left = 0;
        int right = r * c - 1;

        while(left <= right){
            int mid = left + (right - left)/2;

            int value = matrix[mid / c][mid % c];

            if(value == target){
                return true;
            }
            else if(value < target)

                left = mid + 1;
            else
                right = mid -1;
        }
        return false;
    }
}

Problem Solution In C++

class Solution {
public:
    bool searchMatrix(vector <vector<int> >& matrix, int target) {
        int row = matrix.size(), col = matrix[0].size();
        int left = 0, right = row * col - 1;
        while (left <= right)
        {
            int mid = left +(right - left)/2;
            int r = mid / col, c = mid % col;
            if (matrix[r][c]==target) return true;
            if (matrix[r][c] < target)
                left = mid +1;
            else
                right = mid -1;
        }
        return false;
    }
};

Problem Solution In C

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
    int totalRow=matrixSize;
    if(totalRow==0 || *matrixColSize==0)
    {
        return false;
    }
    
    int start=0;
    int end=matrixSize*(*matrixColSize)-1;
    int row=0;
   
    int col= 0;
   
    int mid=0;
    
    while(start<=end)
    {
        mid=(start+end)/2;
        
        row=mid/(*matrixColSize);
        
        col=mid%(*matrixColSize);
        
        
        if(matrix[row][col]==target)
        {
            return true;
        }
        
        else if(matrix[row][col]>target)
        {
            end=mid-1;
        }
        
        else
        {
            start=mid+1;
        }
    }
    
    return false;
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment