# Search for a target value in a 2D Matrix

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

```Input:
matrix = [
[1,   3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]

target = 11
Output: true```

Binary Search:

the input matrix `m x n` could be considered as a sorted array of length `m x n`. So we can use Binary Search in the 2D matrix with a little trick to calculate the index of the `mid` element.

```int pivot = left + (right-left)/2;
int pivotElement = matrix[pivot/width][pivot%width];```

The following diagram is a pictorial representation of the logic to find the  `mid` element.

```public boolean searchMatrix(int[][] matrix, int target) {

int height = matrix.length;
if (height == 0) return false;
int width = matrix.length;

int left = 0;
int right = (height * width - 1);
while (left <= right) {
int pivot = left + (right - left) / 2;
int pivotElement = matrix[pivot / width][pivot % width];
if (target == pivotElement) {
return true;
} else {
if (target > pivotElement) left = pivot + 1;
else right = pivot - 1;
}
}
return false;
}
```

Complexity Analysis

• Time Complexity: `O(log(mn))` since it’s a standard binary search.
• Space Complexity: `O(1)`.

Categories: Binary Search