# 1. Introduction

In this blog post, we'll explore a problem often encountered in the realm of matrix manipulation - searching for an element in a matrix that is sorted both row-wise and column-wise. This problem is a great example of how to efficiently navigate through a structured data set.

## Problem

Given an m x n matrix where every row and column is sorted in increasing order, find the position of a target value in the matrix if it is present. If the target value is not present in the matrix, print “Not Found”.

Example 1:

```Input: matrix[4][4] = { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};
target = 29
Output: Found at (2, 1)
Explanation: Element at (2,1) is 29
```

Example 2:

```Input : matrix[4][4] = { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};
target = 100
```

# 2. Solution Steps

1. Start searching from the top-right corner of the matrix.

2. If the current element is greater than the target, move left.

3. If the current element is less than the target, move down.

4. If the target is found, return its position.

5. If the end of the row or column is reached without finding the target, print "Not Found".

# 3. Code Program

``````public class Solution {

// Main method for testing
public static void main(String[] args) {
int[][] matrix = { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};
int target1 = 29;
searchElement(matrix, target1); // Search for 29

int target2 = 100;
searchElement(matrix, target2); // Search for 100
}

// Method to search the element in the matrix
public static void searchElement(int[][] matrix, int target) {
int i = 0;
int j = matrix[0].length - 1;

while (i < matrix.length && j >= 0) {
if (matrix[i][j] == target) {
System.out.println("Found at (" + i + ", " + j + ")");
return;
}
if (matrix[i][j] > target) {
j--;
} else {
i++;
}
}
}
}
``````

### Output:

```Found at (2, 1)