杨氏矩阵搜索算法

问题：已知一个2维矩阵，其中的元素每一行从左至右依次增加，每一列从上到下依次增加。即对于矩阵Table有Table[i][j] ≤Table[i][j + 1], Table[i][j] ≤ Table[i + 1][j]，我们也称这样的矩阵为杨氏矩阵。给出判定某个数是否存在该矩阵中的高效算法。

分析：为了便于复杂度分析，我们暂时假定该矩阵为大小n*n。如下图所示为一个杨氏矩阵。

二分搜索解法：

许多人都观察到了矩阵在二维上都是有序的，所以使用在每一行（或者每一列）使用二分搜索是很自然的想法。由于每一行二分搜索需要O(lgn)时间，搜索n行需要O(nlogn)的时间。显然这个时间复杂度还是不够高效。当然这只是第一步尝试，不要让自己过早的陷入到二分搜索的泥潭中，好的方法还在后面。

一种错误的想法：

如果不细心也许会掉入一个陷阱中。有人也许认为可以先从行来判定，如果某个数位于某2行间，则只需要检查相应的2列即可，这是错误的。如下左边图所示，假定我们需要查找9是否在矩阵中，由于9位于7到11之间，所以接下来在7和11的这两列中（这2列在图中高亮显示）二分查找9，虽然能够查找到9，虽然查找9成功了，但是这个方法是错误的。因为10也位于7到11之间，但是10并不在这2列中。

即便是如下右边图示查询范围包括2行2列，尽管在查找9和10都成功，但是还是错误的，反例大家可以自己找一个。

Step-wise线性搜索解法：

从右上角开始，每次将搜索值与右上角的值比较，如果大于右上角的值，则直接去除1行，否则，则去掉1列。如下图显示了查找13的轨迹。首先与右上角15比较，13<15，所以去掉最右1列，然后与11比较，这是13>11，去掉最上面1行…以此类推，最后找到13。算法复杂度O(n)，最坏情况需要2n步，即从右上角开始查找，而要查找的目标值在左下角的时候。

代码如下：

[cpp] view plaincopy

1. bool stepWise( int mat[][N_MAX], int N, int target,
2. int &row, int &col) {
3. if (target < mat[0][0] || target > mat[N-1][N-1]) return false ;
4. row = 0;
5. col = N-1;
6. while (row <= N-1 && col >= 0) {
7. if (mat[row][col] < target)
8. row++;
9. else if (mat[row][col] > target)
10. col--;
11. else
12. return true ;
13. }
14. return false ;
15. }

四分分解算法：

通过观察很容易发现该题可以使用分治法来解决。可以看到，矩阵的中间元素总是将矩阵分成了4个子矩阵。如下图所示，中间元素9将矩阵分成了4个小矩阵,这4个小矩阵在行和列上面都是排好序的，所以原问题可以分解为4个子问题。进一步观察可以发现，每次可以排除掉1个子矩阵，也就是说只要考虑3个子问题即可。如查找目标元素为13，则13>9，因为左上角的子矩阵都小于9，所以左上角的子矩阵可以不用再查询，只需要查询剩下的3个子矩阵即可。同理，当查找元素为6时，由于6<9，因为右下角的子矩阵都大于9，因此可以直接排除右下角的子矩阵，只需要查询其他3个子矩阵即可。当然，如果中间元素等于查询的目标元素，则直接返回即可，否则在剩下的3个子矩阵中查询。

该算法代码如下,注意边界条件，代码中加粗的部分不可省略，否则会导致代码不可终止。l==r&&u==d表示矩阵中只有一个元素，此时若不等于目标元素target，则必须返回false。

[cpp] view plaincopy

1. bool quadPart( int mat[][N_MAX], int M, int N, int target, int l, int u, int r, int d, int &targetRow, int &targetCol) {
2. if (l > r || u > d) return false ;
3. if (target < mat[u][l] || target > mat[d][r]) return false ;
4. int col = l + (r-l)/2;
5. int row = u + (d-u)/2;
6. if (mat[row][col] == target) {
7. targetRow = row;
8. targetCol = col;
9. return true ;
10. } else if (l == r && u == d) {
11. return false ;
12. }
13. if (mat[row][col] > target) {
14. return quadPart(mat, M, N, target, col+1, u, r, row, targetRow, targetCol) ||
15. quadPart(mat, M, N, target, l, row+1, col, d, targetRow, targetCol) ||
16. quadPart(mat, M, N, target, l, u, col, row, targetRow, targetCol);
17. } else {
18. return quadPart(mat, M, N, target, col+1, u, r, row, targetRow, targetCol) ||
19. quadPart(mat, M, N, target, l, row+1, col, d, targetRow, targetCol) ||
20. quadPart(mat, M, N, target, col+1, row+1, r, d, targetRow, targetCol);
21. }
22. }
24. bool quadPart( int mat[][N_MAX], int N, int target, int &row, int &col) {
25. return quadPart(mat, N, N, target, 0, 0, N-1, N-1, row, col);
26. }

该算法复杂度是多少呢？可以通过公式计算：

原文公式： T(n) = 3T(n/2) + c, 
T(n) = 3T(n/2) + c,  = 3 [ 3T(n/4) + c ] + c  = 3 [ 3 [ 3T(n/8)  + c ] + c ] + c = 3k T(n/2k) + c (3k - 1)/2        = 3k ( T(n/2k) + c ) - c/2 Setting k = lg n,  T(n)  = 3lg n ( T(1) + c ) - c/2       = O(3lg n)       = O(nlg 3)           <== 3lg n = nlg 3 = O(n1.58) 

注：我以为这里公式应该是T(n) = 3 * T(n/4) + c ，不对的话请大家指正。 

update：从维度来看，确实是原文的正确。

二分算法：

这个算法我们从矩阵中间行或者中间列或者对角线开始查找，找到s满足

 ai < s < ai+1 ,  其中ai为矩阵中的值。

a）从中间行查找，如查找10位于9到16之间。

b）从中间列查找，如查找10位于9到14之间。

c）从对角线查找，查找10位于9到17之间。

显然不管从哪里查找，都可以将原矩阵分成2个子矩阵，这样就分成了2个子问题，比起四分分解法的3个子问题，这个方法应该更好。

代码如下，注意这里代码确定范围用的是线性查找，实际可以通过二分查找加速整个过程。

[cpp] view plaincopy

1. bool binPart( int mat[][N_MAX], int M, int N, int target, int l, int u, int r, int d, int &targetRow, int &targetCol) {
2. if (l > r || u > d) return false ;
3. if (target < mat[u][l] || target > mat[d][r]) return false ;
4. int mid = l + (r-l)/2;
5. int row = u;
6. while (row <= d && mat[row][mid] <= target) {
7. if (mat[row][mid] == target) {
8. targetRow = row;
9. targetCol = mid;
10. return true ;
11. }
12. row++;
13. }
14. return binPart(mat, M, N, target, mid+1, u, r, row-1, targetRow, targetCol) ||
15. binPart(mat, M, N, target, l, row, mid-1, d, targetRow, targetCol);
16. }
18. bool binPart( int mat[][N_MAX], int N, int target, int &row, int &col) {
19. return binPart(mat, N, N, target, 0, 0, N-1, N-1, row, col);
20. }

T（n) = 2T(n/4)+cn

如果采用二分查找确定范围，则T(n)=2T(n/4)+clgn