即对于矩阵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步，即从右上角开始查找，而要查找的目标值在左下角的时候。
【代码】
- bool stepWise(int mat[][N_MAX], int N, int target,
- int &row, int &col) {
- if (target < mat[0][0] || target > mat[N-1][N-1]) return false;
- row = 0;
- col = N-1;
- while (row <= N-1 && col >= 0) {
- if (mat[row][col] < target)
- row++;
- else if (mat[row][col] > target)
- col--;
- else
- return true;
- }
- return false;
- }
四分分解算法：
通过观察很容易发现该题可以使用分治法来解决。可以看到，矩阵的中间元素总是将矩阵分成了4个子矩阵。如下图所示，中间元素9将矩阵分成了4个小矩阵,这4个小矩阵在行和列上面都是排好序的，所以原问题可以分解为4个子问题。进一步观察可以发现，每次可以排除掉1个子矩阵，也就是说只要考虑3个子问题即可。如查找目标元素为13，则13>9，因为左上角的子矩阵都小于9，所以左上角的子矩阵可以不用再查询，只需要查询剩下的3个子矩阵即可。同理，当查找元素为6时，由于6<9，因为右下角的子矩阵都大于9，因此可以直接排除右下角的子矩阵，只需要查询其他3个子矩阵即可。当然，如果中间元素等于查询的目标元素，则直接返回即可，否则在剩下的3个子矩阵中查询。
该算法代码如下,注意边界条件，代码中加粗的部分不可省略，否则会导致代码不可终止。l==r&&u==d表示矩阵中只有一个元素，此时若不等于目标元素target，则必须返回false。
- bool quadPart(int mat[][N_MAX], int M, int N, int target, int l, int u, int r, int d, int &targetRow, int &targetCol) {
- if (l > r || u > d) return false;
- if (target < mat[u][l] || target > mat[d][r]) return false;
- int col = l + (r-l)/2;
- int row = u + (d-u)/2;
- if (mat[row][col] == target) {
- targetRow = row;
- targetCol = col;
- return true;
- } else if (l == r && u == d) {
- return false;
- }
- if (mat[row][col] > target) {
- return quadPart(mat, M, N, target, col+1, u, r, row, targetRow, targetCol) ||
- quadPart(mat, M, N, target, l, row+1, col, d, targetRow, targetCol) ||
- quadPart(mat, M, N, target, l, u, col, row, targetRow, targetCol);
- } else {
- return quadPart(mat, M, N, target, col+1, u, r, row, targetRow, targetCol) ||
- quadPart(mat, M, N, target, l, row+1, col, d, targetRow, targetCol) ||
- quadPart(mat, M, N, target, col+1, row+1, r, d, targetRow, targetCol);
- }
- }
- bool quadPart(int mat[][N_MAX], int N, int target, int &row, int &col) {
- return quadPart(mat, N, N, target, 0, 0, N-1, N-1, row, col);
- }
该算法复杂度是多少呢？可以通过公式计算：
原文公式： 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 ，不对的话请大家指正。
二分算法：
这个算法我们从矩阵中间行或者中间列或者对角线开始查找，找到s满足
ai < s < ai+1 , 其中ai为矩阵中的值。
a）从中间行查找，如查找10位于9到16之间。
b）从中间列查找，如查找10位于9到14之间。
c）从对角线查找，查找10位于9到17之间。
显然不管从哪里查找，都可以将原矩阵分成2个子矩阵，这样就分成了2个子问题，比起四分分解法的3个子问题，这个方法应该更好。
代码如下，注意这里代码确定范围用的是线性查找，实际可以通过二分查找加速整个过程。
- bool binPart(int mat[][N_MAX], int M, int N, int target, int l, int u, int r, int d, int &targetRow, int &targetCol) {
- if (l > r || u > d) return false;
- if (target < mat[u][l] || target > mat[d][r]) return false;
- int mid = l + (r-l)/2;
- int row = u;
- while (row <= d && mat[row][mid] <= target) {
- if (mat[row][mid] == target) {
- targetRow = row;
- targetCol = mid;
- return true;
- }
- row++;
- }
- return binPart(mat, M, N, target, mid+1, u, r, row-1, targetRow, targetCol) ||
- binPart(mat, M, N, target, l, row, mid-1, d, targetRow, targetCol);
- }
- bool binPart(int mat[][N_MAX], int N, int target, int &row, int &col) {
- return binPart(mat, N, N, target, 0, 0, N-1, N-1, row, col);
- }
该方法复杂度的分析：为了方便，假定最后查找的子矩阵为分成了2个相同大小的子矩阵,且都为原来1/4大小。
T（n) = 2T(n/4)+cn
如果采用二分查找确定范围，则T(n)=2T(n/4)+clgn
英文原文地址：http://www.leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html
