算法设计：二维数组，横向纵向均递增，如何查找n是否在数组里？？

这个题在笔试中经常会考到，这里做个总结。思路就是，从矩阵的最右上角的元素开始扫描a[i][j]，如果要查找的数n小于该元素，则让i--，即往左移动一个数据再比较。如果n大于该数，则让j++，让原来的数往下移动一个数接着比较。 这里的设计思路就是充分利用了，数组横向纵向都递增的规律。而且巧妙的，一次只改变行数或列数，对应的列数或行数保持不变来进行搜索。 这和二维数组的螺旋打印异曲同工，待杂家有时间再总结螺旋打印问题。

时间复杂度最差为m+n，最好为m或者n。

程序如下：

#include  <iostream>using namespace std;#define N 10#define M 10int main(){int a[N][M];int n;int i = 0, j = M-1;while(i<N && j>=0){if(n < a[i][j])j--;else if(n > a[i][j])i++;else{cout<<"已找到！i = "<<i<<"j = "<<j<<endl;    return 0;}}return -1; //表示未找到}