[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组合的左下角出发为例，解法如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { public: bool searchMatrix(vector<vector<int> > &matrix, int target) { if(!matrix.size() || !matrix[0].size()) return false; int m = matrix.size(), n = matrix[0].size(); int row = m-1, col = 0; //left bottom corner while(row>=0 && col<n) { if(target<matrix[row][col]) row--; else if(target>matrix[row][col]) col++; else return true; } return false; } };