搜索二维矩阵

难度：⭐⭐ 面试常见

考点

• 二维矩阵展平为一维的二分
• 坐标转换：index → (row, col)

题目描述

给你一个满足下述两条属性的 m x n 整数矩阵：

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

给定整数 target，判断它是否在矩阵中。

函数签名

func searchMatrix(matrix [][]int, target int) bool

示例

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

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

要求

1. 时间复杂度 O(log(m*n))

提示

• 将二维矩阵视为一维有序数组进行二分
• 一维下标 mid → 行 mid/n，列 mid%n

---

参考答案（Go）

点击展开参考答案

//go:build ignore

package answer

func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return false
	}
	m, n := len(matrix), len(matrix[0])
	left, right := 0, m*n-1
	for left <= right {
		mid := left + (right-left)/2
		val := matrix[mid/n][mid%n]
		if val == target {
			return true
		} else if val < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return false
}