# 74. Search a 2D Matrix

## LeetCode [**74. Search a 2D Matrix**](https://leetcode-cn.com/problems/search-a-2d-matrix/)\*\*\*\*

### Description

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.

![](https://3979976701-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MWCWmbVhbhatBCAMIGH%2Fuploads%2Fgit-blob-af8d9b552c024364e276c9c61d6cb0813302bfd1%2Fimage%20\(7\).png?alt=media)

**Example 1:**

```
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
```

**Example 2:**

```
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
```

**Constraints:**

* `m == matrix.length`
* `n == matrix[i].length`
* `1 <= m, n <= 100`
* `-104 <= matrix[i][j], target <= 104`

### Tags

Binary Search, Array

### Solution

This is a 2D version of Binary Search problem. Based on the Binary Search template, we only need to convert any 1D index to 2D, with the formula below, so that we can position that element in the given matrix.

$$Flattened1DArray\[i] = 2DMatrix\[i/cols]\[i\pmod{cols}]$$

### Complexity

* Time complexity: $$O(log(n))$$
* Space complexity: $$O(1)$$

### Code

```go
func searchMatrix(matrix [][]int, target int) bool {
	rows, cols := len(matrix), len(matrix[0])
	start, end := 0, rows*cols-1
	for start+1 < end {
		mid := start + (end-start)/2
		if center := matrix[mid/cols][mid%cols]; center > target {
			end = mid
		} else if center < target {
			start = mid
		} else {
			return true
		}
	}
	if matrix[start/cols][start%cols] == target || matrix[end/cols][end%cols] == target {
		return true
	}
	return false
}
```
