100% beats with the optimal Binary search Solution
Intuition
The problem involves searching for a target value in a 2D matrix where each row and column is sorted in ascending order. My initial thought is to util
Intuition
The problem involves searching for a target value in a 2D matrix where each row and column is sorted in ascending order. My initial thought is to utilize the properties of the matrix to efficiently locate the target without checking every element. A common approach is to start from the top-right corner of the matrix and adjust our position based on comparisons.
Approach
Start at Top-Right Corner: Begin the search at the top-right corner of the matrix. This allows us to make decisions based on whether the current element is greater than or less than the target.
Comparison Logic:
If the current element equals the target, return true.
If the current element is less than the target, move down to the next row (increase the row index).
If the current element is greater than the target, move left to the previous column (decrease the column index).
Termination Condition: The search continues until either the target is found or we move out of bounds of the matrix (i.e., when row exceeds n-1 or col becomes negative).
Return Result: If we exit the loop without finding the target, return false.
This method leverages the sorted nature of both rows and columns, allowing for an efficient search.
Complexity
Time Complexity: The time complexity is 
O(n+m)
O(n+m), where n
n is the number of rows and m
m is the number of columns. In the worst case, we may traverse one entire row and one entire column.
Space Complexity: The space complexity is 
O(1)
O(1) since we are using only a constant amount of extra space for variables.
# Code
```cpp []
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n=matrix.size();
        int m=matrix[0].size();
       int row=0,col=m-1;
       while(row<n && col>=0){
         if(matrix[row][col]==target){
            return true;
         }else if(matrix[row][col]<target){
            row++;
         }else{
            col--;
         }
       }
       return false;
    }
};
```
['C++']