个人评价：排序数组，不难想到二分查找，熟悉后扩展，一维=>二维 也就不难了~

题目难度：🌟 🌟 （参考 LeeCode 简单🌟 、中等🌟 🌟 、困难🌟 🌟 🌟 ）

另，通常算法题会考察分析时间复杂度和空间复杂度，可参考笔者之前的文章

「数据结构&算法」必知必会系列：3. 时间 & 空间复杂度（下）

搜索二维矩阵

题目描述

74. 搜索二维矩阵

编写一个高效的算法来判断 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 n == matrix[i].length 1 <= m, n <= 100 -104 <= matrix[i][j], target <= 104

解题思路

思路不难，参考如下（二维二分查找）：

  • 如果目标数大于行最小，且小于行最大，在该行内查找
  • 行内查找，使用二分法
  • 行数确认，亦使用二分

一维数组二分查找不难理解，Golang 代码如下：

// 一维数组二分查找
func searchLine(line []int, target int) bool {
    left, right := 0, len(line)-1
    for left <= right {						// 二分法退出条件，注意！<<
        mid := left + (right - left) >> 1	// >> 1 向下取整(/2)
        if line[mid] == target {
            return true
        } else if line[mid] > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return false
}

行数确认也类似，参考 Golang 代码如下：

func searchMatrix(matrix [][]int, target int) bool {
    n := len(matrix)
    m := len(matrix[0])		// n > 1，确保存在 matrix[0]
    low, high := 0, n - 1
    for low <= high {
        mid := low + (high - low) >> 1
        lineMin := matrix[mid][0]
        lineMax := matrix[mid][m-1]
        if lineMin <= target && lineMax >= target {
            return searchLine(matrix[mid], target)
        } else if lineMin > target {
            high = mid - 1
        } else if lineMax < target {
            low = mid + 1
        }
    }
    return false
}

总结

个人感觉还是算简单的，二分查找（搜索）的经典写法理应是熟知的~

  1. 循环退出条件：注意是 low <= high，而不是 low < high
  2. mid 的取值，mid := low + (high - low) >> 1
  3. low 和 high 的更新，low = mid + 1，high = mid - 1

Add to CheatSheet 😁