喜刷刷: [LeetCode] Search a 2D Matrix

喜刷刷: [LeetCode] Search a 2D Matrix

[LeetCode] Search a 2D Matrix

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.

For example,

Consider the following matrix:

[    [1,   3,  5,  7],    [10, 11, 16, 20],    [23, 30, 34, 50]  ]  

Given target = 3, return true.

思路：分别搜索判断行坐标和列坐标。

找出上下左右四个边界上元素的规律特点：

1. 左边界：A[i,0]为row i  ~ row m-1的最小值。
当target < A[i, 0]时，在row 0 ~ row i-1中继续搜索。反之则无法判断，因为row 0 ~ row i-1中也可能存在比A[i, 0]大的数。

2. 右边界：A[i, n-1]为row 0 ~ row i的最大值。

当target > A[i, n-1]时，在row i+1 ~ row m-1中继续搜索。同理反之则无法判断。

3. 上边界：A[0, j]为col j ~ col n-1的最小值。

当target < A[0,j]时，在col 0 ~ col j-1中继续搜索。反之则无法判断。

4. 下边界：A[m-1, j]为col 0 ~ col j的最大值。

当target > A[m-1, j]时，在col j+1 ~ col n-1中继续搜索。反之则无法判断。

发现对于每个边界点而言，总有一种大小关系是无法排除区域的，而搜索时我们希望通过一次和target的比较就能减小搜索区域。这里的窍门是，矩阵的四个顶点中的任意一个(i, j)都同时在两个边界上。我们希望这两个边界的条件组合能提供：无论target < A[i,j]还是target > A[i,j]都能缩小搜索范围。观察以上四个边界，发现1,4的组合或2,3的组合都能符合。

1，4组合对应左下角：target < A[i, j]时，向上搜索；反之向右搜索

2，3组合对应右上角：target < A[i, j]时，向左搜索；反之向下搜索

以1，4组合的左下角出发为例，解法如下：

Read full article from 喜刷刷: [LeetCode] Search a 2D Matrix