🎯 Three Approaches || 🔥 Very Easy Detailed Solution || 🎯 JAVA || 🎯  C++
Approach 1: Staircase Search (or Binary-like Search)
Start from the top-right corner of the matrix.
Compare the current element (matrix[row][col]) with target:
# Approach 1: Staircase Search (or Binary-like Search) 
<!-- Describe your approach to solving the problem. -->
1. **Start from the top-right corner of the matrix.**
2. **Compare the current element (matrix[row][col]) with target:**
    - If it matches, return true.
    - If it is smaller, move down (increase row).
    - If it is greater, move left (decrease col).
3. **Continue until either:**
    - The element is found.
    - row goes out of bounds (row >= n).
    - col goes out of bounds (col < 0).
4. **If the loop completes, return false (element not found).**
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$O(n + m)$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$O(1)$
# Code
```java []
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length, m = matrix[0].length;
        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++ []
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size(), 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;
    }
};

```
# Approach 2: Binary Search
<!-- Describe your approach to solving the problem. -->
1. **Binary Search Function (search):**
    - It performs binary search on a 1D array (arr) to check if target is present.
    - If found, it returns true; otherwise, it continues the search.
    - If the loop ends, it returns false.

2. **Iterate Over Each Row (searchMatrix):**
    - Iterate through all n rows of the matrix.
    - For each row, call the search function to check if target is present.
    - If found in any row, return true; otherwise, return false after checking all rows.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$O(n * log(m))$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$O(1)$
# Code
```java []
class Solution {
    private boolean search(int arr[], int n, int target){
        int low=0, high=n-1;
        while(low <= high){
            int mid = low + (high - low)/2;
            if(arr[mid] == target) return true;
            else if(arr[mid] < target) low = mid+1;
            else high = mid-1;
        }
        return false;
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length, m = matrix[0].length;
        for(int i=0; i<n; i++){
            if(search(matrix[i], m, target)){
                return true;
            }
        }
        return false;
    }
}
```
```C++ []
class Solution {
private:
    bool search(vector<int>& arr, int target) {
        int low = 0, high = arr.size() - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) return true;
            else if (arr[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return false;
    }

public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size(), m = matrix[0].size();
        for (int i = 0; i < n; i++) {
            if (search(matrix[i], target)) {
                return true;
            }
        }
        return false;
    }
};

```

# Approach 3: Brute Force
<!-- Describe your approach to solving the problem. -->
1. Iterate through each row (i from 0 to n-1).
2. Iterate through each column (j from 0 to m-1) inside each row.
3. Check if the current element (matrix[i][j]) is equal to target:
    - If yes, return true (target found).
    - If no, continue checking the next elements.
4. If the loop completes without finding the target, return false.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$O(n*m)$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$O(1)$
# Code
```java []
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length, m = matrix[0].length;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(matrix[i][j] == target) return true;
            }
        }
        return false;
    }
```
```C++ []
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size(), m = matrix[0].size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == target) return true;
            }
        }
        return false;
    }
};
```
['Array', 'Math', 'Binary Search', 'Matrix', 'Simulation', 'C++', 'Java']