Search a 2D Matrix

You are given an m x n integer matrix matrix with the following two properties:

• Each row is sorted in non-decreasing order.

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

• Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Solutions

public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        
        int row=0;
        int col=matrix[0].Length-1;
        
        while(row<matrix.Length && col>=0){
            
            if(matrix[row][col]==target){
                return true;
                
            }
            
            if(matrix[row][col]>target){
                col--;
            }
            else{
                row++;
            }
        }
        return false;
        
    }
}

The time complexity of this algorithm is O(N+M), where N is the number of rows and M is the number of columns in the input matrix. This is because the algorithm starts from the top right corner of the matrix and moves either left or down in each iteration of the while loop. In the worst case, it will move all the way to the bottom left corner of the matrix, which takes N+M-2 steps.