Search a 2D Matrix
最后更新于：2022-04-02 01:08:58
# Search a 2D Matrix
### Source
- leetcode: [Search a 2D Matrix | LeetCode OJ](https://leetcode.com/problems/search-a-2d-matrix/)
- lintcode: [(28) Search a 2D Matrix](http://www.lintcode.com/en/problem/search-a-2d-matrix/)
### Problem
Write an efficient algorithm that searches for a value in an *m* x *n* matrix.
This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
#### Example
Consider the following matrix:
~~~
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
~~~
Given `target = 3`, return `true`.
#### Challenge
O(log(n) + log(m)) time
### 题解 - 一次二分搜索 V.S. 两次二分搜索
- **一次二分搜索** - 由于矩阵按升序排列，因此可将二维矩阵转换为一维问题。对原始的二分搜索进行适当改变即可(求行和列)。时间复杂度为 O(log(mn))=O(log(m)+log(n))O(log(mn))=O(log(m)+log(n))O(log(mn))=O(log(m)+log(n))
- **两次二分搜索** - 先按行再按列进行搜索，即两次二分搜索。时间复杂度相同。
显然我们应该选择一次二分搜索，直接上 lower bound 二分模板。
### Java
~~~
public class Solution {
/**
* @param matrix, a list of lists of integers
* @param target, an integer
* @return a boolean, indicate whether matrix contains target
*/
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0] == null) {
return false;
}
int ROW = matrix.length, COL = matrix[0].length;
int lb = -1, ub = ROW * COL;
while (lb + 1 < ub) {
int mid = lb + (ub - lb) / 2;
if (matrix[mid / COL][mid % COL] < target) {
lb = mid;
} else {
if (matrix[mid / COL][mid % COL] == target) {
return true;
}
ub = mid;
}
}
return false;
}
}
~~~
### 源码分析
仍然可以使用经典的二分搜索模板(lower bound)，注意下标的赋值即可。
1. 首先对输入做异常处理，不仅要考虑到matrix为null，还要考虑到matrix[0]的长度也为0。
1. 由于 lb 的变化处一定小于 target, 故在 else 中判断。
### 复杂度分析
二分搜索，O(logn)O(\log n)O(logn).
';