LeetCode-热题100：74. 搜索二维矩阵

题目描述

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

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 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
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

代码及注释

下面是给每一句代码加上注释并解释为什么要这么做的代码：

func searchMatrix(matrix [][]int, target int) bool {
    // 获取矩阵的行数m和列数n
    m, n := len(matrix), len(matrix[0])  
    // 遍历矩阵的每一行
    for i := 0; i < m; i++ {  
    	// 检查目标值是否可能在当前行中
        if matrix[i][0] <= target && matrix[i][n - 1] >= target {  
        	// 初始化左右指针
            left, right := 0, n - 1  
            // 二分查找目标值
            for left <= right {  
                mid := (left + right) / 2
                // 找到目标值
                if matrix[i][mid] == target {  
                    return true
                } else if matrix[i][mid] > target {  // 目标值在左半部分
                    right = mid - 1
                } else {  // 目标值在右半部分
                    left = mid + 1
                }
            }
        } 
    }
    return false  // 在整个矩阵中未找到目标值
}

代码解释

1. 获取矩阵的行数m和列数n:

   m, n := len(matrix), len(matrix[0])
   

   通过这两个变量，我们可以确定矩阵的大小，以便遍历每一行和每一列。

2. 遍历矩阵的每一行:

   for i := 0; i < m; i++ {
   

   这里通过遍历每一行，我们尝试确定目标值可能存在的行。

3. 检查目标值是否可能在当前行中:

   if matrix[i][0] <= target && matrix[i][n - 1] >= target {
   

   这一步是为了减少搜索的范围。如果目标值小于当前行的最小值或大于当前行的最大值，则该行不可能包含目标值。

4. 二分查找目标值:

   left, right := 0, n - 1
   for left <= right {
       mid := (left + right) / 2
       if matrix[i][mid] == target {
           return true
       } else if matrix[i][mid] > target {
           right = mid - 1
       } else {
           left = mid + 1
       }
   }
   

   在确定了可能包含目标值的行后，我们使用二分查找来在这一行中找到目标值。

5. 在整个矩阵中未找到目标值:

   return false
   

   如果整个矩阵都被遍历了，但没有找到目标值，那么就返回false。

这种方法的时间复杂度是O(mlogn)，其中m是矩阵的行数，n是矩阵的列数。