# 74.M 搜索二维矩阵

## 题目

> <https://leetcode-cn.com/problems/search-a-2d-matrix/>

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

**每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。**

示例 1：

```
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 
输出：true 
```

示例 2：

```
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 
输出：false
```

提示：

* m == matrix.length&#x20;
* n == matrix\[i].length&#x20;
* 1 <= m, n <= 100&#x20;
* -104 <= matrix\[i]\[j], target <= 104

## 解题思路

二分查找。

把每一行拼接到上一行的末尾，就可以得到一个一维的递增序列，对这个递增序列进行二分查找即可。与普通二分查找的区别是，需要把mid映射为行号和列号。

## 实现代码

```go
func searchMatrix(matrix [][]int, target int) bool {
	rows := len(matrix)
	cols := len(matrix[0])
	left := 0
	right := rows * cols - 1
	for left <= right {
		mid := left + (right - left) / 2
		row := mid / cols
		col := mid % cols
		if matrix[row][col] == target {
			return true
		} else if matrix[row][col] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return false
}
```