一天一道算法题（32）：搜索二维数组

74. 搜索二维矩阵

文章目录

• [74. 搜索二维矩阵](https://leetcode.cn/problems/search-a-2d-matrix/)
• • ==四种解题思路==
  • • 第一种：暴力枚举（O(m·n)）
    • 第二种：逐行二分（O(m·log n)）
    • 第三种：两次二分（O(log m + log n) = O(log(m·n))）
    • 第四种：模拟一维数组
  • 总结

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

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

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

你必须编写一个时间复杂度为 O(log(m * 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

四种解题思路

接下来我会带着你，从 O(m·n) 一步步优化到 O(log(m·n))。

第一种：暴力枚举（O(m·n)）

嵌套 for 循环逐个判断，都没匹配就返回 false。这种做法一定会超时，也不符合题目要求，这里不展开。

第二种：逐行二分（O(m·log n)）

对每一行各做一次二分查找。这是最常见的优化思路，但它适用于“行与行之间整体不保证严格递增”的情况——比如下一行第一个元素不一定大于上一行最后一个元素。而这道题的二维数组整体是严格升序的，所以这个做法还不够，需要继续优化。

第三种：两次二分（O(log m + log n) = O(log(m·n))）

从这里开始，才是这道题能 AC 的解法。

思路是：第一次二分确定 target 如果存在，应该在哪一行；第二次二分在这一行里继续找。两次二分就能定位到 target。

• Java 代码演示

class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int rowIndex = binarySearchFirstColumn(matrix, target);
if (rowIndex < 0) {
return false;
}
return binarySearchRow(matrix[rowIndex], target);
}

public int binarySearchFirstColumn(int[][] matrix, int target) {
int low = –1, high = matrix.length – 1;
while (low < high) {
int mid = (high – low + 1) / 2 + low;
if (matrix[mid][0] <= target) {
low = mid;
} else {
high = mid – 1;
}
}
return low;
}

public boolean binarySearchRow(int[] row, int target) {
int low = 0, high = row.length – 1;
while (low <= high) {
int mid = (high – low) / 2 + low;
if (row[mid] == target) {
return true;
} else if (row[mid] > target) {
high = mid – 1;
} else {
low = mid + 1;
}
}
return false;
}
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/search–a–2d–matrix/solutions/688117/sou–suo–er–wei–ju–zhen–by–leetcode–solut–vxui/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

• Golang 代码演示

func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return false
}

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

// 第一次二分：定位行
// 找第一个满足 matrix[row][n-1] >= target 的行
top, bottom := 0, m–1
for top < bottom {
mid := top + (bottom–top)/2
if matrix[mid][n–1] < target {
top = mid + 1
} else {
bottom = mid
}
}
row := top

// 第二次二分：在该行内查找
left, right := 0, n–1
for left <= right {
mid := left + (right–left)/2
if matrix[row][mid] == target {
return true
} else if matrix[row][mid] < target {
left = mid + 1
} else {
right = mid – 1
}
}

return false
}

第四种：模拟一维数组

如果把二维数组按元素个数“摊平”，对上面那个 3×4 的数组来说，几乎所有人都会把第一行第一个元素当作第 1 个元素，把第三行第四个元素当作第 12 个元素。我们就按这个逻辑模拟一维数组——整个数组长度为 12。

那问题来了：怎么把这个“脑海中模拟的一维数组”和真实的二维数组做映射？

这里直接给公式：

matrix[mid / n][mid % n] 稍微推演一下就能明白：mid / n 定位行，mid % n 定位列。

好，现在按这个思路写代码。

Java 代码演示

class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int low = 0, high = m * n – 1;
while (low <= high) {
int mid = (high – low) / 2 + low;
int x = matrix[mid / n][mid % n];
if (x < target) {
low = mid + 1;
} else if (x > target) {
high = mid – 1;
} else {
return true;
}
}
return false;
}
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/search–a–2d–matrix/solutions/688117/sou–suo–er–wei–ju–zhen–by–leetcode–solut–vxui/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Golang 代码演示

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

总结

本文是 《算法题目解析系列》 的第 [32] 篇，本系列将持续更新，每篇都提供清晰的思路与编程语言实现。欢迎关注，第一时间获取更新。如果你有想看的题目，也可以在评论区留言告诉我。