搜索二维矩阵

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

解题思路：

1. 遍历每个单词，并将每个单词的某一个字符变为*，构建虚拟单词，并构建原单词与虚拟单词的连线

2. 若两个单词之间只差一个字符，那么必然能通过虚拟单词将两个单词连通

3. 因此只需要从beginWord开始，通过广度优先遍历，找到与endWord相同的虚拟单词，即可找到最短路径

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)$。