> For the complete documentation index, see [llms.txt](https://leetcodebook-1.gitbook.io/top-interview-150/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcodebook-1.gitbook.io/top-interview-150/binary-search/search-a-2d-matrix.md).

# 搜索二维矩阵

题目链接: <https://leetcode.cn/problems/search-a-2d-matrix>

## 解题思路：

1. 遍历每个单词，并将每个单词的某一个字符变为`*`，构建虚拟单词，并构建原单词与虚拟单词的连线
2. 若两个单词之间只差一个字符，那么必然能通过虚拟单词将两个单词连通
3. 因此只需要从`beginWord`开始，通过广度优先遍历，找到与`endWord`相同的虚拟单词，即可找到最短路径

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

func searchRow(data [][]int, target int) int {
	left, right := 0, len(data)-1
	for left < right {
		rowMid := (right-left)/2 + left
		if data[rowMid][0] <= target {
			left = rowMid
		} else {
			right = rowMid - 1
		}
	}
	return left
}
```

## 复杂度分析

* **时间复杂度：** 时间复杂度为$$O(log mn)$$, $$m$$为矩阵的行数，$$n$$为举证的列数。
* **空间复杂度：** 空间复杂度为$$O(1)$$。


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcodebook-1.gitbook.io/top-interview-150/binary-search/search-a-2d-matrix.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.