学步园

 先看一个来自算法导论习题里6-3与剑指offer的一道编程题（也被经常用作面试题，本人此前去搜狗二面时便遇到了）：

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字6，则返回true；如果查找数字5，由于数组不含有该数字，则返回false。

1 2
8 9

2 3 912

4 7
10 13

6 8
11 15

本Young问题解法有三（如查找数字6）：

1.递归，代码如下：

#include "stdio.h"

static int arr[4][4]={{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
int width = 4, height = 4;

bool search_in_young_matrix(int arr[][4], int x, int y, int target)
{
	if((x==width)||(y==height))
		return false;
	if(target<arr[x][y])
		return false;
	if(target==arr[x][y])
		return true;
	else
	{
		return search_in_young_matrix(arr,x+1,y,target) || search_in_young_matrix(arr,x+1,y,target);
	}
}

int main()
{
	if( search_in_young_matrix(arr,0,0,4) )
		printf("%s", "I found it!");
	else
		printf("%s", "Sorry. Item doesn't exist!");
	int i;
	scanf("%d",&i);
}

2.分治法：

通过观察很容易发现该题可以使用分治法来解决。可以看到，矩阵的中间元素总是将矩阵分成了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);
}