## Search an element in a sorted 2d matrix

Write an efficient algorithm that searches for a value in an `m x n` matrix. The 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.

Example 1:

``````Input:
matrix = [
[1,  5,  9,  11],
[13, 16, 19, 24],
[28, 30, 38, 50]
]
target = 5
Output: true
``````

Example 2:

``````Input:
matrix = [
[1,  5,  9,  11],
[13, 16, 19, 24],
[28, 30, 38, 50]
]
target = 12
Output: false
``````

## Sorted Matrix search solution in Java

The naive approach of searching for an element in a 2D matrix is to just iterate over every element of the matrix and check if a matching element is found or not. This approach will have a time complexity of `O(m*n)`.

But, since the matrix is sorted, we can use binary search and find the element in `O(log(m*n))` time. The following solution uses binary search:

``````class MatrixSearch {
private static boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0) {
return false;
}

int numRows = matrix.length;
int numCols = matrix.length;

int left = 0, right = numRows*numCols - 1;

while(left <= right) {
int mid = (left+right)/2;
int midValue = matrix[mid/numCols][mid%numCols];
if(target == midValue) {
return true;
} else if (target < midValue) {
right = mid-1;
} else {
left = mid+1;
}
}

return false;
}

public static void main(String[] args) {
int[][]matrix = {
{1, 5, 9, 11},
{13, 16, 19, 24},
{28, 30, 38, 50}
};

int target = 5;

System.out.println(searchMatrix(matrix, 5));
}
}
``````
``````# Output
\$ javac MatrixSearch.jaava
\$ java MatrixSearch
true
``````